Optimising n!
If you want to add up all the numbers from 1 to n, you can do it two ways. The slow, inefficient way is to calculate:
1 + 2 + 3 + ... + n
The quick way is to remember what you were taught in school, that:
1 + 2 + 3 + 4 + 5 + 6 = (6 + 1) + (2 + 5) + (3 + 4) = 7 + 7 + 7
and that in general:
1 + 2 + ... + n = n(n+1)/2
This optimisation might not matter for small values of n, but for n = 1000000 it really makes a big difference. This got me thinking whether there was a similar trick for calculating the product of all numbers from 1 to n - that is, n-factorial, or n!.
This matters even more for n! because it gets so large so quickly that computers are unable to accurately represent the intermediate values. In fact, 20! is the largest that can be respresented on a 64 bit machine. 21! can only be approximated, as you need to use a floating point number. This means that not only is calculating really big factorials time-consuming, it's not possible at all to do it accurately with native datatypes.
I don't even know if there is a simple re-statement of n! like there is for the sum above, but I'm gonna spend a few idle minutes working on it.
Posted by [anonymous] on Sun, 22 Jun 2008 at 20:30:59