## 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 aI'm an A!>>> a.x = 3>>> print a.x3>>> print a.__dict__{'x': 3, '__repr__': }`

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 bprint b('x')print b['y']`

Run it:

 `> python script.py rep: 3call: 3, xget: 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.py0 11 12 23 64 245 1206 7207 50408 403209 362880`

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

 `> python factorial.py5000 1632610000 3566015000 5613020000 7733825000 99094`

25,000 factorial has nearly 100,000 digits!