Implement Russian Peasant Multiplication in C++

The Russian Peasant multiplication is used to multiply two numbers without using the multiplication operator. It involves constant use of halving and doubling the numbers.

In this article, we have two integers, our task is to find the product of these two integers by implementing russian peasant multiplication in C++.

Steps to Implement Russian Peasant Multiplication

We will follow these simple steps to find the product using Russian Peasant multiplication:

• We have created a function russianPeasant() that accepts both the numbers (n and m) as arguments.
• Then we used a while loop that runs till m>0. The while loop checks if m is odd.
• If m is odd, then the n is added to the result.
• We have used the left shift and right shift bitwise operators to double and halve the numbers respectively.
• This process of doubling and halving the number continues until m becomes 0.

Implementing Russian Peasant Multiplication in C++

Below is the C++ code to implement russian peasant multiplication:

#include <iostream>
using namespace std;

unsigned int russianPeasant(unsigned int n, unsigned int m) {
    unsigned int result = 0;
    while (m > 0) {
        if (m & 1) {  // If m is odd
            result = result + n;
        }
        n = n << 1;  // Double n
        m = m >> 1;  // Halve m
    }
    return result;
}

int main() {
    cout << "Multiplication of 10 and 20: " 
         << russianPeasant(10, 20) << endl;  
    cout << "Multiplication of 7 and 6: " 
         << russianPeasant(7, 6) << endl;   
    return 0;
}

The output of the above code is:

Multiplication of 10 and 20: 200
Multiplication of 7 and 6: 42