[prev in list] [next in list] [prev in thread] [next in thread] 

List:       koffice-devel
Subject:    Re: facrtorial functions in kspread
From:       Benoît_Jacob <jacob () math ! jussieu ! fr>
Date:       2008-11-17 23:24:35
Message-ID: 200811180024.38765.jacob () math ! jussieu ! fr
[Download RAW message or body]

On Monday 17 November 2008 08:36:47 Andrew wrote:
> 2. the code uses a recursive implementation.  Yuck.  See for example
> http://stackoverflow.com/questions/231250/how-would-you-write-a-non-recursi
>ve- algorithm-to-calculate-factorials

Not that it is going to help much making a great KOffice 2.0 release, but just 
FWIW, i'd like to mention that none of the approaches above touch the point 
that, for any given degree of precision, computing n! has O(1) complexity and 
not O(n) as all the approaches in your link have (they all do basically the 
same naive approach of multiplying integers togethers).

Start from the formula n! = Gamma(n+1) where Gamma is the Euler Gamma function 
(check wikipedia or mathworld). So all you need is asymptotic estimates of 
Gamma(x) as x tends to +infinity. A rough starting point is Stirling's 
formula which tells you that

n! is equivalent to sqrt(2*pi*n) * (n/e)^n

http://en.wikipedia.org/wiki/Stirling's_approximation
http://en.wikipedia.org/wiki/Factorial#Computation

Cheers,
Benoit
_______________________________________________
koffice-devel mailing list
koffice-devel@kde.org
https://mail.kde.org/mailman/listinfo/koffice-devel
[prev in list] [next in list] [prev in thread] [next in thread]