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