Multiply Integers Using Russian Peasant Algorithm in Python

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 where 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 python.

 

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: How To Install Python on Windows 11

 

Python Program To Multiply Integers Using Russian Peasant Algorithm

 

Input:

20, 12

Output:

240

 

# A method to multiply two numbers
# using Russian Peasant method

# Function to multiply two numbers
# using Russian Peasant method
def russianPeasant(a, b):

    res = 0 

    # Till 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

# Driver program to test
# above function
print(russianPeasant(20, 12))