Home » C++ programs

C++ program to multiply two numbers without using multiplication operator

Here, we are going to learn how to multiply two numbers without using multiplication operator using Russian peasant algorithm?
Submitted by Vivek Kothari, on November 17, 2018

The problem is we have two integer numbers and find the multiplication of them without using the multiplication operator. This problem can be solved using the Russian peasant algorithm. Assume the two given numbers are m and n. Initialize mul with 0 and repeat following steps while n is greater than zero :

1. Add m to mul, if n is odd
2. Double the value of m and half the value of n.

Here we use properties of << (left shift) and >> (right shift) operators for doubling the value of m and for dividing the value of ‘n by 2.

Reference: Russian peasant multiplication

C++ program to implement Russian peasant algorithm

#include <iostream> 
using namespace std; 

int Multiply(int m, int n) 
{
	int mul=0; 

	while (n > 0) 
	{
		// if n is odd
		if (n & 1) mul = mul + m; 

		// Double 'm' and halve 'n' 
		m = m << 1; 
		n = n >> 1; 
	} 

	return mul;
} 

int main() {
	int ans;

	ans=Multiply(2,3);
	cout<<"Multiplication of 2 and 3 = "<<ans<<endl;

	ans=Multiply(10,10);
	cout<<"Multiplication of 10 and 10 = "<<ans<<endl;

	return 0; 
} 

Output

Multiplication of 2 and 3 = 6
Multiplication of 10 and 10 = 100