Factorials
Bengt Richter
bokr at oz.net
Sat Sep 20 16:20:16 EDT 2003
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
More information about the Python-list
mailing list