# [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 ⊥