The Russian Peasant Multiplication is an ancient technique for multiply two integers. Its algorithm is very interesting and allows to compute the multiplication only with sums, shift left and shift right operations.
As an example to illustrate how Peasant works, let's multiply 5 by 6. To do this, we will put the numbers in two columns and then we divide by two the number of the first column until it reaches 1. At the same time, we multiply by two the number of the second column. The result of the multiplication is the sum of the numbers of the second column when the numbers of the first column are odd. Try it again for 6x5 and the result will be the same!
Why does it work?
The product of two integer numbers can be expressed according to the equation (1):
Returning to the example of multiply 5 by 6, let's call a=5 and b=6. In the first iteration of the algorithm, a is odd and b is added to the multiplication result. In each step the value of a is divided by 2 and b is multiplied by 2. This occurs until a reaches the value 1.
In the second iteration, a=2 and b=12, and since a is an even number it is not added to the multiplication result. Finally, in the third iteration a=1 and the value of b=24 is added to the result of the product, which is 30 and the algorithm stops.
Note through the figure bellow that the process of multiplying by 6 and 5 is very similar. It is important to see that the algorithm has log2(a) iterations and swapping a by b if a > b optimizes the calculation of the Peasant.
The peasant algorithm is illustrated in the figure below. To check if a binary number is odd just make sure the least significant bit is 1, otherwise, if it is 0, the number is even. Thus, the expression C=C+A&B accumulates the value of B only when A is an odd number.
You want to practice? Check out the SystemVerilog implementation of Peasant module and its testbench:
Also available in GitHub.