Thursday, February 10, 2011

Memoizing the factorial in Python

A Python class can be defined very simply:


>>> class A:  pass
...
>>> a = A()
>>> print a
<__main__.A instance at 0x424670>



>>> def f():  return "I'm an A!"
...
>>> a.__repr__ = f
>>> print a
I'm an A!
>>> a.x = 3
>>> print a.x
3
>>> print a.__dict__
{'x': 3, '__repr__': <function f at 0x1ee3b0>}


Of course it would be more typical to define some state for objects of the class, and perhaps also an inheritance hierarchy. Save this in script.py:


class A(object):
def __init__(self,n):
self.n = n
def __repr__(self):
return str(self.n)

a = A(3)
print a


Run it from the command line:


> python script.py 
3


Two other standard Python operators are the "getitem" operator [ ], and the "call" operator ( ). These can be implemented for any user-defined class:


class B(object):
def __init__(self,n):
self.n = n

def __repr__(self):
return 'rep: ' + str(self.n)

def __call__(self,arg):
return 'call: %d, %s' % (self.n, arg)

def __getitem__(self,arg):
return 'get: %d, %s' % (self.n, arg)

b = B(3)
print b
print b('x')
print b['y']


Run it:


> python script.py 
rep: 3
call: 3, x
get: 3, y


I wrote a simple class to implement the factorial function that uses the call operator. This class keeps the values it currently knows in a list. (Apparently, this technique is called memoization). If we knew that we only wanted the last value, it would be better not to do this..


class factorial:
def __init__(self):
self.L = [1,1]
def __call__(self,n):
if type(n) != type(2) or n < 0:
raise ValueError('invalid number')
L = self.L
i = len(L) - 1
while i < n:
i += 1
L.append(L[-1]*i)
return L[n]

f = factorial()
for i in range(10):
print i, f(i)



> python factorial.py
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880



def test():
for i in range(0,26000,5000):
current = len(str(f(i)))
print i, current

test()



> python factorial.py
5000 16326
10000 35660
15000 56130
20000 77338
25000 99094


25,000 factorial has nearly 100,000 digits!