Multiply Integers Using Russian Peasant Algorithm in C++

It’s quite amusing to see how different variations of solutions for the same questions are thereby different individuals. From pretty ancient times maths has played a very vital role in civilizations. Not to mention how everything around us revolves mathematically. Now programming is more or less similar to that. It’s the second version of maths were to solve real-world problems you need to apply real-world mathematical concepts. However, as we’re talking about maths, the Russian Peasant Algorithm of multiplication is known by very few individuals. Therefore today let’s write a simple program to Multiply Integers Using Russian Peasant Algorithm in C++.

 

What is the Russian Peasant Algorithm?

 

• The basic concept of the Russian Peasant Algorithm is to multiply two numbers by successive addition of the first number with itself.

 

• However, while the number is being added the second number is being reduced to half each time the first number is added.

 

• This process is continued till the second number gets reduced to less than 1.

 

What’s The Approach?

 

• Let us consider the numbers a & b to be multiplied with each other.

 

• The final result of Multiplication will be stored in the result variable res which will initially be assigned 0.

 

• Till the value of b is greater than 0 if b is odd no then add a to res.

 

• Otherwise, if b is even then, double a and reduce b to half.

 

• To perform addition and reduction of numbers we’ll use bitwise shift operators.

 

Also Read: Print Fibonacci Series using C++

 

C++ Program To Multiply Integers Using Russian Peasant Algorithm

 

Input:

20, 12

Output:

240

 

#include <iostream>
using namespace std;

// A method to multiply two numbers using the Russian Peasant method
unsigned int russianPeasant(unsigned int a, unsigned int b)
{
    int res = 0; // initialize result

    // While the second number doesn't become 1
    while (b > 0)
    {
        // If the 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;
}

// Driver program to test above function
int main()
{
    
    cout << russianPeasant(20, 12) << endl;
    return 0;
}