[Python-Dev] Why no math.fac?

Tim Peters tim.one@comcast.net
Sat, 24 Aug 2002 16:03:13 -0400

[Gerhard H=E4ring]
> Any reason why there isn't any factorial function in the math modul=

math has traditionally just wrapped functions from the platform libm,
although it's gotten a *little* smarter than that in a few ways.

> I could easily implement one in C (for ints and longs only, right?)

A Python function is more suitable.  If n is small, fac goes fast no =
how it's written.  If n is large, the time spent in long-int multipli=
will overwhelming swamp whatever little savings you got from writing =
it in
C.  More, an intelligent unbounded-int fac function written in Python=
likely run much faster than anything you could bear to code in C, bec=
ause an
"intelligent" function for this would strive to balance the sizes of =
multiplicands along the way, and that requires bookkeeping that's pai=
nful in

For example, try these under current CVS Python:

=66rom heapq import heapreplace, heappop

def fac1(n):
    if n =3D=3D 0:
        return 1
    if n <=3D 2:
        return n
    partials =3D range(2, n+1)
    while len(partials) > 1:
        n1 =3D heappop(partials)
        n2 =3D partials[0]
        heapreplace(partials, n1*n2)
    return partials[0]

def fac2(n):
    if n =3D=3D 0:
        return 1
    if n <=3D 2:
        return n
    result =3D 2
    for i in xrange(3, n+1):
        result *=3D i
    return result

fac1 implements a simple balancing scheme that eventually manages to =
Karatsuba multiplication (new in 2.3; the heapq module is also new) i=
play.  For n=3D100000, fac2 takes 10 times longer to run on my box, a=
wouldn't be significantly faster than that if coded in C.