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
bto be multiplied with each other.
- The final result of Multiplication will be stored in the result variable
initially be assigned 0.
- Till the value of
bis greater than
oddno then add
- Otherwise, if
bis even then, double
- 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
# 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))