Russian peasant multiplication algorithm

algorithm
multiplication
matrix-multiplication
russian-peasantalgorithm

(Team) #1

Russian peasant multiplication is an interesting way to multiply numbers that uses a process of halving and doubling without using multiplication operator. The idea is to double the first number and halve the second number repeatedly till the second number does not become 1. In the process, whenever the second number become odd, we add the first number to result.

Read this article to understand the basic idea behind Russian peasant multiplication algorithm with an example

This algorithm works on the bitwise level and hence, utilizes bitwise operators to multiply two numbers. The time complexity of the Russian Peasant Multiplication algorithm is O(log N).

Have a doubt or thought? Feel free to comment below


This is a companion discussion topic for the original entry at http://iq.opengenus.org/russian-peasant-multiplication-algorithm/