<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> <HTML> <HEAD> <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-2022-jp"> <META NAME="Generator" CONTENT="MS Exchange Server version 6.5.7036.0"> <TITLE>RE: [racket] Math - factorial.rkt, binomial.rkt and memoization</TITLE> </HEAD> <BODY>    Thanks for your interesting replies. It was just my first thought. Jos > -----Original Message----- > From: users-bounces@racket-lang.org > [<A HREF="mailto:users-bounces@racket-lang.org">mailto:users-bounces@racket-lang.org</A>] 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 > >> <<A HREF="http://en.wikipedia.org/wiki/Stirling%27s_approximation">http://en.wikipedia.org/wiki/Stirling%27s_approximation</A>> > 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 $B"](J > > ____________________ >   Racket Users list: >   <A HREF="http://lists.racket-lang.org/users">http://lists.racket-lang.org/users</A> > </BODY> </HTML>