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.pyclass 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.pyimport 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 |
