ChatterBank1 min ago
Russian peasant's algorithm
Can anyone tell me why it works..? (p.s I do know how to do it)
Answers
1 to 3 of 3
Best Answer
No best answer has yet been selected by D-Jas. Once a best answer has been selected, it will be shown here.
For more on marking an answer as the "Best Answer", please visit our FAQ.
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.
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.
1 to 3 of 3
Related Questions
Sorry, we can't find any related questions. Try using the search bar at the top of the page to search for some keywords, or choose a topic and submit your own question.