Binary multiplication in Python

I came across a question on Stack OverFlow that references binary multiplication. This is a fun problem for a beginning Python coder.

Let's say we want to multiply 3 x 5 in binary:

00101 ( 5) x 00011 ( 3) ------- 00101 ( 5) + 01010 (10) ------- 01111 (15)

Let's talk generally by substituting m x n (so here m = 3 and n = 5).

No matter what the value of m, we will end up by adding together a series of bit-shifted versions of n, here: 00101 and 01010

5 = 00101
3 = 00011 = 2**0 + 2**1
3 x 5 = (5 << 0) + (5 << 1)

For any m, we require the set of exponents i, j, k.. such that:

2**i + 2**j + 2**k + ... = m

[This has to be done from the "top down." First find the largest power of 2 that is less than m, record that exponent, and take m = m % 2**e to continue... It's tricky, and that's why I took the easy way out, below.]

Now we sum

n << i
+ n << j
+ n << k
+ ... = m x n

It's very helpful that Python will do bit-shifting on ints:

>>> 5 << 1 10

I spent a while debugging code to generate the needed exponents, before I decided to cheat (a bit) by using binary representation:

>>> bin(3) '0b11'

The first function below returns the exponents i,j,k...
The second does the bit-shifting. For efficiency, we do the factoring on the smaller of the two operands.

import random def binary_exps(n): L = list(bin(n)[2:]) L.reverse() L = [i for i,c in enumerate(L) if c == '1'] return L def multiply(x,y): if y > x: x,y = y,x result = 0 L = binary_exps(y) for e in L: result += x << e return result, L if __name__ == '__main__': for i in range(1, 10): n = 2**i-1 L = binary_exps(n) print str(n).rjust(4), L assert n == sum([2**e for e in L]) print for i in range(20): x = random.choice(range(1000)) y = random.choice(range(1000)) prod, L = multiply(x,y) print str(x).rjust(4), str(y).rjust(4), L assert prod == x * y

$ python multiply_binary.py 1 [0] 3 [0, 1] 7 [0, 1, 2] 15 [0, 1, 2, 3] 31 [0, 1, 2, 3, 4] 63 [0, 1, 2, 3, 4, 5] 127 [0, 1, 2, 3, 4, 5, 6] 255 [0, 1, 2, 3, 4, 5, 6, 7] 511 [0, 1, 2, 3, 4, 5, 6, 7, 8] 406 819 [1, 2, 4, 7, 8] 902 817 [0, 4, 5, 8, 9] 755 115 [0, 1, 4, 5, 6] 963 170 [1, 3, 5, 7] 526 836 [1, 2, 3, 9] 236 228 [2, 5, 6, 7] 504 448 [6, 7, 8] 438 840 [1, 2, 4, 5, 7, 8] 225 791 [0, 5, 6, 7] 373 512 [0, 2, 4, 5, 6, 8] 307 230 [1, 2, 5, 6, 7] 672 565 [0, 2, 4, 5, 9] 389 137 [0, 3, 7] 444 406 [1, 2, 4, 7, 8] 587 707 [0, 1, 3, 6, 9] 412 246 [1, 2, 4, 5, 6, 7] 390 307 [0, 1, 4, 5, 8] 269 368 [0, 2, 3, 8] 146 553 [1, 4, 7] 90 182 [1, 3, 4, 6]