Peasant's Multiplication Algorithm
Exploit the binary representation of the number. eg:
98 * 19
Take one of the two number and represent it in binary. Now, what happens
= 98 * (1 0 0 1 1)
= 98 * (16 + 2 + 1)
= 98 * 16 + 98 * 2 + 98 * 1
= 1568 + 196 + 98
= 1862
Calculate by hand or calculator
= 98 * 19
= 1862
What is the usefulness ?
Computation of multiplication is not as easy as addition, subtraction, shift operations or logical operations. Many primitive microprocessor and micro-controller doesn't
even support it directly. So, one way of doing it is by adding a term to itself for the number of second term. eg if x*y then if we add x to itself y times then we get x*y,
However, the computation has to be done y times. But same thing can be achieved by using this algorithm but still we are doing three multiplications in above example instead of
one. But the trick is all the multiplication above is multiplication by the power of 2 and which is very cheap to compute which can be achieved easily by shifting the bits.
C Code:
#include<stdio.h>
int mult(int a,int b)
{
int count = 0,sum=0;
while(b != 0)
{
if((b & 1)!= 0)
sum += a << count;
b = b >> 1;
count++;
}
return sum;
}
int main()
{
int num1,num2;
scanf("%d%d",&num1,&num2);
printf("%d x %d = %d\n",num1,num2,mult(num1,num2));
return 0;
}
