Factorials

[Anton Vredegoor]

Tim Rowe <tim at remove_if_not_spam.digitig.cix.co.uk> wrote:

>Well, I don't have a pressing need for this, so I think I'll wait
>until 2.3 comes out of beta :-)

Pressing needs are just signals indicating that personal history is
about to be redefined :-)

Anyway, I've retroactively redefined my functions to be compliant with
Python22 and I've also used another timing routine. See the code
below. I'm using a kind of test driven development where the tests are
like: "Is this code interesting?". So I write some code, apply the
test, change the code, run the *same* test (a definite advantage of
ambiguous tests) on it again, etc.

I'm providing some output from the script, first when run under
Python23 an then under Python22.

Some observations:

- Python23 is a lot faster for this script than Python22
- The "karagen" generator is faster but only by a small factor.
- Python22 is not precomputing 2**2000 but Python23 is? See the
"strange" value for the Python22 output in top of the most right
column.
- Using the zipped iterator is faster for large n, even on Python22
- Optimized multiplications for longs only works in Python23 *and* if
*both* integers are big? Is this the other secret of the zipped
iterator?
- For large factorials Python23's optimized multiplications can give
very large speed benefits, in the output below the fast script is
about 15 times faster for n = 70000 .
- The speed difference could become arbitrarily large for even higher
factorials.

Anton

output columns are:

1) n: argument to the factorial function
2) timing for fac(n) (i.e. "reduce(long.__mul__, range(2,n+1),1L)" )
3) timing for fac1(n) (zipped iterator)
4) timing for fac2(n) (zipped iterator and using karagen's
aggregation)

Now after letting the script run on an AMD1800 under Win98Se:

>d:\python23\pythonw -u test3.py
    0)  0.000  0.000  0.000
 5000)  0.099  0.054  0.025
10000)  0.376  0.140  0.082
15000)  0.844  0.262  0.164
20000)  1.526  0.394  0.230
25000)  2.420  0.531  0.378
30000)  3.536  0.738  0.525
35000)  5.259  0.858  0.711
40000)  7.838  1.151  0.842
45000) 10.780  1.391  1.071
50000) 14.098  1.583  1.279
55000) 17.837  1.995  1.476
60000) 22.006  2.299  1.793
65000) 26.838  2.660  2.088
70000) 32.110  2.732  2.338
>Exit code: 0
>d:\python22\pythonw -u test3.py
    0)  0.002  0.000  0.238
 5000)  0.130  0.091  0.062
10000)  0.521  0.356  0.289
15000)  1.194  0.713  0.602
20000)  2.144  1.271  1.125
25000)  3.392  2.011  1.832
30000)  4.951  2.973  2.741
35000)  7.343  4.089  3.865
40000) 10.881  5.503  5.173
45000) 14.919  7.106  6.741
50000) 19.504  8.910  8.542
55000) 24.627 11.017 10.504
60000) 30.419 13.329 12.766
65000) 37.007 15.908 15.267
70000) 43.866 18.563 18.014
>Exit code: 0

The code:

from time import clock
from __future__ import generators

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

def fac1(n):
    R = range(2,n+1)+[1]
    while len(R)>1:
        if len(R) % 2: R[0]*=R.pop()
        it = iter(R)
        R=[i*j for i,j in zip(it,it)]
    return R[0]

def karagen(n):
    K = 2**2000
    y = 1
    for x in xrange(2,n+1):
        y *= x
        if y > K:
            yield y
            y = 1
    yield y

def fac2(n):
    R = [x for x in karagen(n)]
    while len(R)>1:
        if len(R) % 2: R[0]*=R.pop()
        it = iter(R)
        R=[i*j for i,j in zip(it,it)]
    return R[0]

def test():
    def stopwatch(f,n):            
        t1 = clock()
        f(n)
        t2 = clock()
        print "%6.3f" %(t2-t1),
    for n in range(0,75000,5000):
        print "%5i)" %(n),
        stopwatch(fac,n)
        stopwatch(fac1,n)
        stopwatch(fac2,n)
        print

if __name__=='__main__':
    test()
    
---

use cases are the root of static typing