Binary Multiplication

Subject:	Binary Multiplication
Date:	Sun, 7 Feb 2010 15:13:02 -0800 (PST)

I decribe an unusual method for multiplying two binary numbers.
The method is not very efficient, but it shows a relationship
between multiplication and the Integer Partition function:
http://en.wikipedia.org/wiki/Integer_partition

To multiply two binary numbers, add together the positions
of bits that are one. To multiple 5 times 6:

210 - bit position
---
101 (5)
110 (6)

5 6
---
0+1=1
0+2=2
2+1=3
2+2=4

The product must have 1's in bit positions 1,2,3, and 4.

43210
-----
11110 (30)

Things get more complicated when there are multiple sums
for the same bit position:

210
---
111 (7)
111 (7)

0+0=0
0+1=1
0+2=2
1+0=1
1+1=2
1+2=3
2+0=2
2+1=3
2+2=4

There are two sums for position 1.
Let Sk be the number of sums that add to k.
The value for the product's position k is (Sk mod 2).
We then carry Floor(Sk/2) to the next position.

S0=1 (1)
S1=2 (0)
S2=3+1 (0)
S3=2+2 (0)
S4=1+2 (1)
S5=0+1 (1)

543210
------
110001 = 32+16+1 = 49

According to the Wiki article, there are
only 5 ways two numbers add up to 7
(including 0+7). This means bit position 7
can never have a carry greater than Floor(5/2)=2.

Has anyone seen something like this before?

Russell
- 2 many 2 count