factorial

fact.py

import psyco
psyco.full()

BASE = 1000000
PROFILE = False

def split1k(s):
    s = str(s)
    ret = []
    b = len(str(BASE))
    while s:
        ret.append(int(s[-b:]))
        s = s[:-b]
    return ret

def add1k(x, amount=1, index = 0):
    if len(x) == index:
        x.append(0)

    y = x[index] + amount

    x[index] = y % BASE
    z = y / BASE
    if z == 0:
        return x

    return add1k(x, z, index + 1)

def mul1k(a, b):
    index1 = 0
    res = []
    for x in b:
        index2 = index1
        for y in a:
            m = x * y
            add1k(res, m, index2)
            index2 = index2 + 1
        index1 = index1 + 1

    return res

def convert1k(val):
    y = val[:]
    y.reverse()
    b = len(str(BASE)) - 1
    return ''.join([str(y[0])] + [str(x).zfill(b) for x in y[1:]])
    
def fact(x):
    val = split1k(x)
    cur = [1]
    ret = [1]
    while cur != val:
        ret = mul1k(cur, ret)
        cur = add1k(cur)

    ret = mul1k(cur, ret)

    return ret 

if __name__ == '__main__':
    import sys
    try:
        x = int(sys.argv[1])
    except:
        x = 725

    if PROFILE:
        import hotshot, hotshot.stats
        prof = hotshot.Profile("profiling.data")
        res = prof.runcall(fact, x)
        prof.close()
        stats = hotshot.stats.load("profiling.data")
        stats.strip_dirs()
        stats.sort_stats('time', 'calls')
        stats.print_stats()
        sys.exit(0)

    print "fact(%s) == " % x, convert1k(fact(x))

output.txt

test.test_fact
  TestFact
    test_add ...                                                           [OK]
    test_convert ...                                                       [OK]
    test_fact ...                                                          [OK]
    test_mul ...                                                           [OK]
    test_split ...                                                         [OK]

-------------------------------------------------------------------------------
Ran 5 tests in 0.006s

PASSED (successes=5)

-------------------------------------------------------------------------------

$ python -m timeit -n 10 -r 3 -s "import fact" "fact.fact(725)"
10 loops, best of 3: 15 msec per loop

test_fact.py

import fact
from twisted.trial import unittest

class TestFact(unittest.TestCase):
    def xtest_split(self):
        self.failUnlessEqual(fact.split1k('12345'), [345, 12])

    def xtest_add(self):
        self.failUnlessEqual(fact.add1k([1]), [2])
        self.failUnlessEqual(fact.add1k([999]), [0, 1])
        self.failUnlessEqual(fact.add1k([999, 1]), [0, 2])
        self.failUnlessEqual(fact.add1k([999, 999, 1]), [0, 0, 2])

    def xtest_mul(self):
        self.failUnlessEqual(fact.mul1k([1], [1]), [1], 't1')
        self.failUnlessEqual(fact.mul1k([2], [3, 1]), [6, 2], 't2')
        self.failUnlessEqual(fact.mul1k([2, 1], [3, 1]), [6, 5, 1], 't3')

    def xtest_convert(self):
        self.failUnlessEqual(fact.convert1k([2,1]), str(1*fact.BASE + 2))

    def test_fact(self):
        self.failUnlessEqual(fact.convert1k(fact.fact('5')), '120')
        self.failUnlessEqual(fact.convert1k(fact.fact('20')),
                             '2432902008176640000')
        self.failUnlessEqual(fact.convert1k(fact.fact('25')),
                             '15511210043330985984000000')