## 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```