Dave's Free Press: Journal

violence, pornography, and rude words for the web generation


Recent posts


Recently commented posts


Journals what I read

geeky politics rant silly religion meta music perl weird drinking culture london language transport sport olympics hacking media maths web photography etiquette spam amazon film bastards books bryar holidays palm telecoms cars travel yapc bbc clothes rsnapshot phone whisky security home radio lolcats deafness environment curry art work privacy iphone linux bramble unix go business engineering kindle gps economics latin anglo-saxon money cars environment electronics
Wed, 11 Jun 2008

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 at 20:10 by David Cantrell
keywords: geeky | maths
Permalink | 1 Comment

This is a spoiler, I suppose... though not for a fast accurate calculation

Posted by [anonymous] on Sun, 22 Jun 2008 at 20:30:59

Sorry, this post is too old for you to comment on it.