[racket] Math - factorial.rkt, binomial.rkt and memoization

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.


  _____  



On Tue, Apr 9, 2013 at 2:42 PM, Matthew Flatt <mflatt at cs.utah.edu> wrote:


 (for/product ([p (in-range (+ m 1) (+ n 1))]) p)



This fact/for variant is a clear winner:
> (time (void (fact/for 1000000)))
cpu time: 6948 real time: 6956 gc time: 964
> (time (void (factorial 1000000)))
cpu time: 9936 real time: 9951 gc time: 3700
> (time (void (fact 1000000)))
cpu time: 8445 real time: 8460 gc time: 2273


But I don't fully understand why a simple (for/product ([p (in-range 1 (add1
n))]) p) is as fast as the iota variants.

I see that the latter makes many more small products, which are certainly
faster, but it also does more products of 2 big numbers, whereas for/product
makes only big*small products. Is that a sufficient reason?


Laurent



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130409/baea1bb2/attachment-0001.html>