Thanks for your interesting replies. It was just my first thought. Jos
> -----Original Message----- > From: users-boun...@racket-lang.org > [mailto:users-boun...@racket-lang.org] On Behalf Of Neil Toronto > Sent: martes, 09 de abril de 2013 22:00 > To: users@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 >
____________________ Racket Users list: http://lists.racket-lang.org/users
