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

List:       koffice-devel
Subject:    Re: facrtorial functions in kspread
From:       Andrew Dorrell <andrew.dorrell () gmail ! com>
Date:       2008-11-18 11:23:10
Message-ID: 4922A59E.5040607 () gmail ! com
[Download RAW message or body]

Benoît Jacob wrote:
> 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).
>   

Yes... except for the ones that use look-up-tables :-)

> 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
>   

Good point!  And also I would not bother implementing it for the reason 
you say.

I guess I was just surprised to find the implementation in kspread was 
recursive.

Regards,


_______________________________________________
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]