Thursday, June 17, 2010

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^4 * 23 + 2^7 * 23

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

No comments:

Post a Comment

About Me

My photo
I'm just this shapeshifting simulation of a critter originally from a little planet in the Slow Zone that you've probably never heard of.