gistfile1.py

# Arbitrary precision Multiplication & Addition -- the slow, slow way

def mul(x, y):
    if len(x) < len(y):
        x, y = y, x
    results = []
    x = list(x)
    y = list(y)
    x.reverse()
    y.reverse()
    n = 0
    while True:
        if not y:
            break
        result = ['0'] * n
        by = int(y.pop(0))
        carry = 0
        for z in x:
            val = str( (int(z) * by) + carry )
            assert len(val) in (1, 2)
            if len(val) == 2:
                carry = int(val[0])
                val = val[1]
            else:
                carry = 0
            result.append(val)
        if carry != 0:
            result.append(str(carry))
        result.reverse()
        n += 1
        results.append(result)
    while len(results) > 1:
        t = add("".join(results[0]), "".join(results[1]))
        results.pop(0)
        results.pop(0)
        results.insert(0, t)
    return "".join(results[0])

def add(x, y):
    if len(x) < len(y):
        x, y = y, x
    # x >= y
    while len(y) != len(x):
        y = '0' + y
    result = []
    carry = 0
    for t, u in zip(reversed(x), reversed(y)):
        a = int(t) + int(u) + carry
        if a >= 10:
            carry = 1
            a = a - 10
        else:
            carry = 0
        result.append(str(a))
    if carry == 1:
        result.append('1')
    return "".join(reversed(result))
    
def test():
    import random
    for i in range(10000):
        x = random.randrange(0, 1000000)
        y = random.randrange(0, 1000000)
        result = add(str(x), str(y))
        assert result == str(x + y), \
               "fail: %d + %d == %d, not %s" % \
               (x, y, x+y, result)
        result2 = mul(str(x), str(y))
        assert result2 == str(x * y), \
               "fail: %d * %d == %d, not %s" % \
               (x, y,  x*y, result2)
test()