Dave's Free Press: Journal

violence, pornography, and rude words for the web generation

 

Recent posts

(subscribe)

Recently commented posts

(subscribe)

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 unix go business engineering kindle gps economics latin anglo-saxon money bramble cars environment electronics
Wed, 27 Aug 2008

Optimising n! - revisited

For the background, see this post.

Late one night I thought that you might be able to simplify n-factorial thus:

`\prod_(i=1)^(\phi(n))p(i)^(\lfloorn/(p(i))\rfloor)`

Where:

  • n is the number whose factorial we wish to calculate;
  • p(i) is the ith prime number;
  • Φ(n) is the number of primes less than or equal to n

Now, without using a lookup table, p() and Φ() are hard to calculate, but at least you'd avoid a lot of the problems that come from using the stupendously big numbers that come as intermediate results in calculating factorials.

Unfortunately, that formula is wrong anyway. It's a restatement of this:

100! = 250 * 333 * 520 * 714 * 119 * ...

which came from noticing that 100! is the product of 50 numbers which have 2 as a prime factor, 33 numbers which have 3 as a prime factor, 20 numbers that have 5 as a prime factor, and so on. Unfortunately, it doesn't take account of numbers like 4 and 18 which have a repeated prime factor - 4, for example, is 2 * 2 and 18 is 2 * 3 * 3. Bother.

Posted at 17:13 by David Cantrell
keywords: geeky | maths
Permalink | 0 Comments

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

Archive