[racket] Math - factorial.rkt, binomial.rkt and memoization

On 04/09/2013 11:41 AM, Hendrik Boom wrote:
> On Tue, Apr 09, 2013 at 08:26:31PM +0200, Jos Koot wrote:
>> Would it be possible to use
>> <http://en.wikipedia.org/wiki/Stirling%27s_approximation> Stirling's
>> approximation for a fast inexact first approximation for factorials of very
>> big numbers and from there quickly get to an exact factorial? (if exactness
>> is required) I don't know for I haven't thought thoroughly about this.
>> Jos.
>
> I don't know of a way take an approximation and by applying some
> operation to it to get a better one.
>
> There are ways to do thie for other functions, like squate root, but I
> don't know one for factorial.

For Newton's method, you'd need a differentiable inverse, but computing 
the gamma function's inverse is hard in the first place.

> But there might be a bound on the error in Stirling's approximation that
> you cna use teo determine whether that's good enough for your
> application (if you have one).

Use the first omitted series term as the signed relative error bound. If 
this is e, then exp(|e|)-1 (which is nearly |e| for small e) is the 
relative error bound after exponentiating.

Stirling's series isn't convergent for any particular n; i.e. for any n 
there's a point at which adding more terms makes the error worse. On the 
other hand, for any fixed number of terms, error decreases as *n* 
increases. So the thing I'd try first is finding the n for which the 
error of the non-polynomial part n * log(n) - n + 1/2 * log(2*pi*n) is 
acceptable, and use its exponential

   n^((2*n+1)/2) * exp(-n) * sqrt(2*pi)

for all greater n. The tricky part would be computing exp(-n) with 
acceptable precision. (In fact, this is where I'd go looking for other 
solutions.)

Neil ⊥