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

From: osmium (r124c4u102_at_comcast.net)
Date: 11/13/03 

Date: Thu, 13 Nov 2003 11:52:36 -0800

Olathe writes:

> > "Ben Pfaff" <blp@cs.stanford.edu> wrote in message
> > news:878ymsm1fa.fsf@pfaff.stanford.edu...
> >
> >>"Adam Russell" <REMOVE_THIS_adamrussell@sbcglobal.net> writes:
> >>
> >>
> >>>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.
> >>
> >>How much precision do you need? n! is approximately sqrt(2 * pi
> >>* n) * (n / e)**n, where e is the base of the natural logarithm,
> >>according to Knuth Vol. 1.
> >
> >
> > Only doing integers and the answer has to be exact. Output will be in
> > string form.
> >
> >
> For pure speed, a 10000-line text-file lookup would be quite simple in
> most programming languages. If they want 56!, you simply return line
> 56. Exact, already in string form, and fairly quick (even quicker for
> multiple queries if you load the file into a string array).
>
> I don't see any reason not to use this method. After all, some
> processors use lookup tables to speed math up.

I would guess that there are a lot of digits in 10000!. Or even in 9999!
Might that be a problem?

Relevant Pages

  • Re: (!?) need fast algorithm for computing factorials
    ... entering. ... >> realize that these numbers will be too large for simple representation, ... Only doing integers and the answer has to be exact. ... string form. ...
    (comp.programming)
  • Re: (!?) need fast algorithm for computing factorials
    ... >>according to Knuth Vol. 1. ... > Only doing integers and the answer has to be exact. ... a 10000-line text-file lookup would be quite simple in ... Exact, already in string form, and fairly quick (even quicker for ...
    (comp.programming)