Factorials

[Julian Tibble]

In article <S6Tab.2$eb4.0 at twister.southeast.rr.com>, M-a-S wrote:
> def factorial_iter(n):
>   s = 1
>   for i in range(2,n+1):
>     s *= i
>   return s

<snip>

> Calculations of 950!, 1000 times each (xrange(1000)) --
> 
> recursion ..... 8.01
> reduction ..... 4.20
> iteration ..... 3.79

Be even faster if you used xrange for the factorial function.
However, apparently reduce builds the list, thereby not
benefitting from the use of xrange:

recursion - 4.7
xrecursion - 0.5
reduction - 5.2
xreduction - 5.2

Can reduce be "fixed"?

Julian


(code I used:)
def recursion(n):
        s = 1
        for i in range(2, n+1):
                s *= i
        return s

def xrecursion(n):
        s = 1
        for i in xrange(2, n+1):
                s *= 1
        return s

def reduction(n):
        return reduce(long.__mul__, range(2, n+1), 1L)

def xreduction(n):
        return reduce(long.__mul__, xrange(2, n+1), 1L)


methods = [ recursion, xrecursion, reduction, xreduction]

import time

for method in methods:
        a = time.time()
        for i in xrange(1000):
                method(950)
        b = time.time()
        print "%s - %.1f" % (method.__name__, b - a)