Given two integers, write a function to multiply them without using multiplication operator.
One interesting method is the Russian peasant algorithm. The idea is to double the first number and halve the second number repeatedly till the second number doesn’t become 1. In the process, whenever the second number become odd, we add the first number to result (result is initialized as 0)
Read full article from Russian Peasant Multiplication | GeeksforGeeks
One interesting method is the Russian peasant algorithm. The idea is to double the first number and halve the second number repeatedly till the second number doesn’t become 1. In the process, whenever the second number become odd, we add the first number to result (result is initialized as 0)
Let the two given numbers be 'a' and 'b' 1) Initialize result 'res' as 0. 2) Do following while 'b' is greater than 0 a) If 'b' is odd, add 'a' to 'res' b) Double 'a' and halve 'b' 3) Return 'res'.
unsigned
int
russianPeasant(unsigned
int
a, unsigned
int
b)
{
int
res = 0;
// initialize result
// While second number doesn't become 1
while
(b > 0)
{
// If second number becomes odd, add the first number to result
if
(b & 1)
res = res + a;
// Double the first number and halve the second number
a = a << 1;
b = b >> 1;
}
return
res;
}