Location Arithmetic - Multiplication

Multiplication

To multiply a pair of binary numbers, first mark the two numbers on the bottom and the right side of the grid. Say we want to multiply 22 (= 10110) by 9 (= 1001).

Now place counters at every "intersection" of vertical and horizontal rows of the 1s in each number.

Notice that each row of counters on the grid is just 22 multiplied by some power of two. In fact, the total value of the counters is the sum of two rows

22*8 + 22*1 = 22*(8+1) = 22*9

So the counters on the board actually represent the product of the two numbers, except it isn't possible to "read off" the answer just yet.

Recall that moving counters diagonally doesn't change the value, so move all the counters on inner squares diagonally until they hit either the bottom row or the left column.

Now we make the same moves we did for addition. Replace two counters on a square with one to its left. If the square is on the left column, replace two counters with one above it. Recall that the value of a square doubles if you move up, so this doesn't change the value on the grid.

Let's first replace the two counters on the second square at the bottom with one to its left which leaves two counters at the corner.

Finally, replace the two counters on the corner with one above it and "read off" the binary number in an L-shaped fashion, starting from the top left down to the bottom left corner, and then over to the bottom right.

Read the counters along the L but don't double count the corner square. You will read the binary result 11000110 = 198 which is indeed 22*9.

Why can we read the binary number in this L-shaped fashion? The bottom row is of course just the first six powers of two, but notice that the leftmost column has the next five powers of two. So we can directly read off an 11 digit binary number from the L-shaped set of 11 squares that lie along the left and bottom sides of the grid.

Our small 6x6 grid can only multiply numbers each up to 63, and in general an nxn grid can multiply two numbers each up to 2n+1-1. This scales very fast, so board with 20 numbers per side, for instance, can multiply numbers each up to a little over two million.