Russian peasant's algorithm

[D-Jas]

Can anyone tell me why it works..? (p.s I do know how to do it)

[tony1941]

If you mean the multiplication method where you successively half and double the multiplier and multiplicand (or vice-versa - it's been a long time!!) it is really converting the numbers to Binary notation and then adding up all the partial products. Just like real computers do!

[gen2]

Firstly, for those who don't know what the Russion Peasant's Algorithm is, it is a method of doing multiplication. Here is an example.

If you want to multiply 47 by 7, you set up two columns as follows:

47 7
23 14
11 28
5 56
2 112
1 224

In the left column, you divide the number by 2 (ignoring remainders) each time until you get to 1. In the right column you double the number each time. Finally you add up all the numbers in the right column that are opposite odd numbers in the left column. In this case, you add 7 + 14 + 28 + 56 + 224 in the right column. The sum of these numbers is 329, which is exactly 47 x 7.

The method works because the left column is effectively converting 47 into its binary equivalent. The odd numbers will give a binary 1 and the even numbers will give a binary 0.
47 is odd so 2^0 = 1
23 is odd so 2^1 = 1
11 is odd so 2^2 = 1
5 is odd so 2^3 = 1
2 is even so 2^4 = 0
1 is odd so 2^5 = 1

So if we write the binary representation of 47 horizontally and multiply by 7 we get:

0 0 1 0 1 1 1 1 x
7

Multiplying from the right (least significant column) we get:
7 x 1 x 2^0 = 7
7 x 1 x 2^1 = 14
7 x 1 x 2^2 = 28
7 x 1 x 2^3 = 56
7 x 0 x 2^4 = 0
7 x 1 x 2^5 = 224
Then adding gives you 329

So you see, only the odd numbers produced 1s in the binary number, and only those contributed to the total of 329.

[NetSquirrel]

Excellent answer.