Will Hamic - 1 year ago 86
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();
timer.Start();

// 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.

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