Will Hamic Will Hamic - 1 year ago 58
C# Question

Why is it faster to calculate the product of a consecutive array of integers by performing the calculation in pairs?

I was trying to create my own factorial function when I found that the that the calculation is twice as fast if it is calculated in pairs. Like this:

Groups of 1: 2*3*4 ... 50000*50001 = 4.1 seconds

Groups of 2: (2*3)*(4*5)*(6*7) ... (50000*50001) = 2.0 seconds

Groups of 3: (2*3*4)*(5*6*7) ... (49999*50000*50001) = 4.8 seconds

Here is the c# I used to test this.

Stopwatch timer = new Stopwatch();

// Seperate the calculation into groups of this size.
int k = 2;

BigInteger total = 1;

// Iterates from 2 to 50002, but instead of incrementing 'i' by one, it increments it 'k' times,
// and the inner loop calculates the product of 'i' to 'i+k', and multiplies 'total' by that result.
for (var i = 2; i < 50000 + 2; i += k)
BigInteger partialTotal = 1;
for (var j = 0; j < k; j++)
// Stops if it exceeds 50000.
if (i + j >= 50000) break;
partialTotal *= i + j;
total *= partialTotal;

Console.WriteLine(timer.ElapsedMilliseconds / 1000.0 + "s");

I tested this at different levels and put the average times over a few tests in a bar graph. I expected it to become more efficient as I increased the number of groups, but 3 was the least efficient and 4 had no improvement over groups of 1.

Bar Plot showing the calculation time with different group amounts.

Link to First Data

Link to Second Data

What causes this difference, and is there an optimal way to calculate this?

Answer Source

The time required to do a BigInteger multiplication depends on the size of the product.

Both methods take the same number of multiplications, but if you multiply the factors in pairs, then the average size of the product is much smaller than it is if you multiply each factor with the product of all the smaller ones.

You can do even better if you always multiply the two smallest factors (original factors or intermediate products) that have yet to be multiplied together, until you get to the complete product.