[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=
e?
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 =
matter
how it's written. If n is large, the time spent in long-int multipli=
cation
will overwhelming swamp whatever little savings you got from writing =
it in
C. More, an intelligent unbounded-int fac function written in Python=
would
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 =
the
multiplicands along the way, and that requires bookkeeping that's pai=
nful in
C.
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 =
get
Karatsuba multiplication (new in 2.3; the heapq module is also new) i=
nto
play. For n=3D100000, fac2 takes 10 times longer to run on my box, a=
nd
wouldn't be significantly faster than that if coded in C.