Factorials

[Bengt Richter]

On Sat, 20 Sep 2003 07:13:54 GMT, "M-a-S" <NO-MAIL at hotmail.com> wrote:

>> "Andrew Wilkinson" <ajw126 at NOSPAMyork.ac.uk> wrote in message
>> >
>> > def fac(n):
>> >     return reduce(long.__mul__, range(1,n+1), 1L)
>> >
>> > ..would probably be a bit quicker. I'm not sure how much quicker though.
>> >
>> > Anyway, hope this is of some use,
>> > Regards,
>> > Andrew Wilkinson
>
>def factorial_rec(n):
>  if n <= 1:
>    return 1
>  else:
>    return n*factorial_rec(n-1)
>
>def factorial_iter(n):
>  s = 1
>  for i in range(2,n+1):
>    s *= i
>  return s
>
>def factorial_rdc(n):
>  return reduce(long.__mul__, range(1,n+1), 1L)
>
>
>Best times (seconds) on Compaq 5430US, Pentium 4, 1.8GHz, 512MB
>Windows XP, Python 2.3 (#46, Jul 29 2003, 18:54:32) [MSC v.1200 32 bit (Intel)] on win32
>
>Calculations of 950!, 1000 times each (xrange(1000)) --
>
>recursion ..... 8.01
>reduction ..... 4.20
>iteration ..... 3.79
>

You could also let the factorial benefit from its own experience, e.g.,

 >>> def factorial(n, cache={}):
 ...     fn = cache.get(n)
 ...     if fn: print 'got cached %s!'%n; return fn
 ...     if n<2: cache[n]=1; return 1
 ...     return cache.setdefault(n, n*factorial(n-1))
 ...
 >>> factorial(4)
 24
 >>> factorial(4)
 got cached 4!
 24
 >>> factorial(3)
 got cached 3!
 6
 >>> factorial(6)
 got cached 4!
 720
 >>> factorial(7)
 got cached 6!
 5040
 >>> factorial(7)
 got cached 7!
 5040
 >>> factorial(10)
 got cached 7!
 3628800
 >>> factorial(9)
 got cached 9!
 362880

Or more concisely:

 >>> def fact(n, cache={}):
 ...     return cache.get(n) or cache.setdefault(n, n<2 and 1 or n*fact(n-1))
 ...
 >>> for i in range(10): print i, fact(i)
 ...
 0 1
 1 1
 2 2
 3 6
 4 24
 5 120
 6 720
 7 5040
 8 40320
 9 362880

Regards,
Bengt Richter