Russian Peasant Arithmetic.

Professor Ferret here!

I just wrote a message on SLU I think I'll post here for posterity... explaining Russian Peasant Arithmetic. Here's the original message by Tess Whitcroft:

How to multiply

After writing down the numbers halve the first one and double the second, writing the new numbers below the preceding ones. If the number being halved is odd, just ignore the remainder. Repeat this operation as long as you can:

177 x 23
88 . 46
44 . 92
22 . 184
11 . 368
5 . 736
2 . 1472
1 . 2944

Now remove from the second column all numbers where the corresponding number in the first column is even:

177 x 23
88 . 46 < remove
44 . 92 < remove
22 . 184 < remove
11 . 368
5 . 736
2 . 1472 < remove
1 . 2944

Then add up the remaining numbers:

23 + 368 + 736 + 2944 = 4071

After a couple of requests for explanation, I ended up posting this:

OK, start with the number 177. In binary that's 10110001.

Dividing by two is equivalent to shifting one bit to the right. 177/2 is 88, that's 1011000.

So, here's what you're doing in binary (LHS is Left Hand Side, RHS is Right Hand Side):

LHS       RHS          LO BIT OF LHS   RHS = 23 * 2^N
10110001  10111        1               23 * 2^0 = 23 * 1 = 23
1011000   101110       0
101100    1011100      0
10110     10111000     0
1011      101110000    1               23 * 2^4 = 23 * 16 = 368
101       1011100000   1               23 * 2^5 = 23 * 32 = 736
10        10111000000  0
1         101110000000 1               23 * 2^7 = 23 * 128 = 2944

Look at the third column I added. That's the LHS number in binary, reversed (read from bottom to top). So the process of dividing extracts the binary equivalent of the number starting from the low bit, by looking at the low bit of the value... the values where the number is odd have a low bit of 1. The values where the number is even have a low bit of 0.

At the same time you're calculating 2^n * LHS by multiplying it by two each time.

So what we've done is this:

177 * 23 is (2^0 + 2^4 + 2^5 + 2^7) * 23

By pulling out the values where it's odd, you've extracted:

2^0 * 23 + 2^4 * 23 + 2^5 * 23 + 2^7 * 23

And because multiplication is distributive... that's the value you want.