Wednesday, August 31, 2011

Binary multiplication, again

I had a lot of fun this afternoon, but all along I knew I was "reinventing the wheel." It's easy when you know where you're going.

I implemented binary multiplication with a class that keeps its data as Python strings like '00100011'. It's probably because I have been re-reading Charles Petzold's book Code, which I think is a classic. In any event, I wrote the class "word" which allows objects to add, multiply and exponentiate themselves. The second file is test.py which exercises the class.

It's a great "simple Python" coding project. We do bit-shifting by hand. If you want to be slick, you could go further by trying to implement fast exponentiation. Here is another example by a guy who obviously knows what he's doing.

A bit of sample output:

> python test.py
x     467
y     327
x + y 00000000 00000000 00000011 00011010 = 794
check 467 + 327 = 794
x * y 00000000 00000010 01010100 10000101 = 152709
check 467 * 327 = 152709
z      3
x**z  00000110 00010010 00010010 00001011 = 101847563
check 467 ** 3 = 101847563

x     995
y     402
x + y 00000000 00000000 00000101 01110101 = 1397
check 995 + 402 = 1397
x * y 00000000 00000110 00011010 01110110 = 399990
check 995 * 402 = 399990
z      3
x**z  00111010 10110111 00001100 10111011 = 985074875
check 995 ** 3 = 985074875

x     897
y     490
x + y 00000000 00000000 00000101 01101011 = 1387
check 897 + 490 = 1387
x * y 00000000 00000110 10110100 11101010 = 439530
check 897 * 490 = 439530
z      4
x**z  10111011 11001001 10001110 00000001 = 3150548481
ran into a slight problem

word.py

class word:
    SZ = 32
    def __init__(self,n):
        if type(n) == type('a'):
            b = n.rjust(word.SZ,'0')
        elif type(n) == type(1):
            b = bin(n)[2:]
        else:
            raise ValueError, "can't do that"
        self.b = b.rjust(word.SZ,'0')
        
    def __repr__(self):
        b = self.b
        s = ' '.join([b[:8], b[8:16], b[16:24], b[24:]])
        s += ' = ' + str(eval('0b' + self.b))
        return s
        
    def __add__(self, a):
        carry = '0'
        rL = list()
        for i in range(len(self.b)-1,-1,-1):
            x = self.b[i]
            y = a.b[i]
            t = x+y
            if (t == '01' or t == '10'):
                if carry == '0':
                    rL.append('1')
                if carry == '1':
                    rL.append('0')
            elif t == '00':
                rL.append(carry)
                carry = '0'
            else:
                assert t == '11'
                if carry == '0':
                    rL.append('0')
                    carry = '1'
                else:
                    rL.append('1')
                    carry = '1'
        if carry == '1':
            raise ValueError, 'overflow'
        rL.reverse()
        return word(''.join(rL))
    
    def __mul__(self, a):
        L = list()
        for i in range(len(self.b)-1,-1,-1):
            x = self.b[i]
            if not x == '1':
                continue
            n = word.SZ - i - 1
            r = word(a.b[n:] + '0'*(n))
            L.append(r)
        res = L.pop(0)
        #print 'start:       ', res
        while L:
            next = L.pop(0)
            #print 'next:        ', next
            res = res + next
            #if L:
                #print 'intermediate:', 
            #else:
                #print 'result:      ',
            #print res
        return res

    def __pow__(self, n):
        res = self
        for i in range(n-1):
            res = res * self
        return res

test.py

import random
from word import word
        
R = range(1000)
N = 10
for i in range(N):
    x = random.choice(R)
    y = random.choice(R)    
    xw = word(x)
    print 'x    ', x
    yw = word(y)
    print 'y    ', y
    
    print 'x + y',
    r = xw + yw
    print r
    S = x+y
    assert S == int(str(r).split()[-1])
    print 'check', x, '+', y, '=', S
    
    print 'x * y',
    r = xw * yw
    print r
    P = x*y
    assert P == int(str(r).split()[-1])
    print 'check', x, '*', y, '=', P
    
    for i in range(2,N*2):
        try:
            r = xw**i
        except ValueError:
            i = i-1
            break
    
    z = i
    print 'z     ', z
    print 'x**z ', r
    E = x**z
    try:
        assert E == int(str(r).split()[-1])
    except AssertionError:
        print 'ran into a slight problem\n'
        continue
    print 'check', x,'**', z, '=', E
    print