Multiply Integers Using Russian Peasant Algorithm in Java

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 Java.

 

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: Check If Two Strings Are Anagram using Java

 

Java Program To Multiply Integers Using Russian Peasant Algorithm

 

Input:

20, 12

Output:

240

 

// Java program for Russian Peasant Multiplication
import java.io.*;

class TechDecodeTutorials
{
    // Function to multiply two
    // numbers using Russian Peasant method
    static int russianPeasant(int a, int b)
    {
        // initialize result
        int res = 0;

        // While second number doesn't become 1
        while (b > 0)
        {
            // If second number becomes odd,
            // add the first number to result
            if ((b & 1) != 0)
                res = res + a;

            // Double the first number
            // and halve the second number
            a = a << 1;
            b = b >> 1;
        }
        return res;
    }
    

    public static void main (String[] args)
    {
        
        System.out.println(russianPeasant(20, 12));
    }
}