Re: [PATCH] Another tweak to the multiplication algorithm

[Siddhesh Poyarekar <siddhesh dot poyarekar at gmail dot com>]

On 14 February 2013 18:49, Joseph S. Myers <joseph@codesourcery.com> wrote:
> to be very system-specific, unless you have a more detailed analysis
> showing that actually the numbers of both multiplications and additions
> have gone down with your approach.  It may also indicate that the original

I've figured out that the number of operations in the inner loop do
decrease.  Here are the details:

The older loop looked like this; I've removed the initial values since
they run just once:

for (; i < k; i++, j--)
  zk += X[i] * Y[j]

So the operations within loop are:

1) Loop terminating condition check
2) Increment i
3) Decrement j
4) Read X[i]
5) Read Y[j]
6) Multiply
7) Add to zk

So total number of operations are 7 * k, since the loop runs k times.

The new loop looks like this:

for (; i < j; i++, j--)
  zk += (X[i] + X[j]) * (Y[i] + Y[j])

where the operations are:

1) Loop terminating condition check
2) Increment i
3) Decrement j
4) Read X[i]
5) Read Y[j]
6) Read X[j]
7) Read Y[j]
8) Add X[i] and X[j]
9) Add Y[i] and Y[j]
10) Multiply
11) Add to zk

That makes it 11 * k / 2 operations since this loop runs just k/2
times.  That makes it a total of 5.5 * k operations, which is less
than the earlier 7 * k.

-- 
http://siddhesh.in