How it Works
What the algorithm described above does is in fact convert one of the two numbers into binary (the number which is halved on every line) and then do the required calculation.
To explain a little better let's take the example 13*9 and let the 13 be the number which we are going to halve. The table we end up with will look like this:
13 9
6 18
3 36
1 72
---
117
Now let's look at a different way of doing the same calculation by converting the "13" into binary.
In binary 13=1101=(1*8)+(1*4)+(0*2)+(1*1)
So to multiply 13 by 9 we could work out the following:
({9*1}*8)+({9*1}*4)+({9*0}*2)+({9*1}*1)
Since we're using binary we're dealing with a lot of 1s and 0s and they are all conveniently irrelevant so the above calculation can be written:
(9*8)+(9*4)+(9*1)
One way to convert a number in base 10 into binary is through the following procedure:
- Take the number you wish to convert. If that number is odd you will get a "1" as the rightmost digit of the binary number if it is even you will get a "0".
- Then halve the number. If you end up with a remainder of one you discard it because you have already accounted for that remainder by putting a "1" in the previous column.
- If the result (the halved number with any remainder discarded) is odd put a "1" in the column to the left of the previous digit, if it is even put in a "0".
- Repeat the process until you reach one.
So for 13 you get a "1" - it's odd. Then a "0" -6 is even. Then a "1" - 3 is odd. Then a "1" - 1 is odd. (If you continue you get infinite zeroes).
So for 13 you get 1011 but this procedure generates values starting from the rightmost column so 1011 should be read as 1101.
Now let's look again at the table and add a few columns.
13 1 9 (9*1)
6 0 18 (9*2)
3 1 36 (9*4)
1 1 72 (9*8)
Now to find the solution all you need to do is multiply the values in the second column by those in the third column and add up all those values. All the Russian peasant system does is miss out the second column (and the fourth) and then cross out all rows that have even numbers in their first column because these would have Os in my second column so they would not affect the final solution.