Re: (!?) need fast algorithm for computing factorials

From: Peter Ammon (peter_ammon_at_rocketmail.com)
Date: 11/07/03 

Date: Fri, 07 Nov 2003 12:25:08 -0800

Adam Russell wrote:

> I am looking for the fastest algorithm for computing factorials (ex:
> 4!=4*3*2*1). This is for a programming contest I am thinking of entering.
> The program to be used is Labview and it needs to compute up to 10000!. I
> realize that these numbers will be too large for simple representation, and
> I think I can handle that. But I believe that simply multiplying each and
> every number probably is not the most efficient algorithm so would like
> advice on any numeric methods that might be quicker.

It may seem obvious, but the fastest algorithm will be a precomputed
lookup table. A quick sum of log_2 n! from n = 1 to 10000 using
Stirling's approximation and rounding up each term up to the nearest
multiple of 8 (so you don't have to use fractional bytes in your
representations), reveals that you'll need ~556163952 bits, which is
around 70 MB for a lookup table, if you use an efficient binary
representation of the results. That would easily fit in the memory of a
modern machine.

-Peter

Relevant Pages

  • Re: (!?) need fast algorithm for computing factorials
    ... > The program to be used is Labview and it needs to compute up to 10000!. ... > realize that these numbers will be too large for simple representation, ... and don't bother multiplying them. ... you can avoid multiplying by an /awful/ lot of numbers. ...
    (comp.programming)
  • Help ! Shopping Cart Problem
    ... >You are trying to round by multiplying by 100 and then dividing by 100. ... If the representation of 9.95, while not exact, had sufficient zeroes at ...
    (comp.lang.javascript)
  • Re: (!?) need fast algorithm for computing factorials
    ... entering. ... >> realize that these numbers will be too large for simple representation, ... >> every number probably is not the most efficient algorithm so would like ... and external code is not allowed. ...
    (comp.programming)
  • Re: Is continuum completely filled up?
    ... repeating sequence of coefficients in their representation; ... change the usual algorithm for multiplying; ... No, that's incorrect. ...
    (sci.math)
  • Re: Beginner question: Precision of floating point arithmetic...
    ... Floating point representation is not exact, ... In fact all floating point units use a binary base, so 0.50 and 0.25 can be ... The solution is to convert your float value, input, into an integer number ... Just multiplying by 100 risks the inaccuracy problem ...
    (comp.lang.c)