[racket] Math - factorial.rkt, binomial.rkt and memoization
Thanks for your interesting replies. It was just my first thought.
Jos
> -----Original Message-----
> From: users-bounces at racket-lang.org
> [mailto:users-bounces at racket-lang.org] On Behalf Of Neil Toronto
> Sent: martes, 09 de abril de 2013 22:00
> To: users at racket-lang.org
> Subject: Re: [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 ⊥
>
> ____________________
> Racket Users list:
> http://lists.racket-lang.org/users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130410/84099886/attachment-0001.html>