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 ⊥
____________________
Racket Users list:
http://lists.racket-lang.org/users
