Cool Algorithms Pt. 1 - Russian Peasant Multiplication

Welcome to the first part of a little series I'm doing called "Cool Algorithms"! Each post will feature a cool algorithm which I will explain how it works and then show you how you can implement the algorithm in Python, C, or JavaScript. Hopefully this will be fun as well as educational for everyone.

Let's get started with the first algorithm that I have chosen, Russian Peasant Multiplication.

Russian Peasant Multiplication

The funny thing about this algorithm is that it really has nothing to do with Russian Peasants - scholars have tried to prove links to Russian Peasants, but they have done so ineffectively. The earliest roots of this algorithm can be traced to ancient Egypt, where an old Egyptian scroll called the Rhind papyrus contained a version of this algorithm.

The purpose of RPM is to help people figure out how to multiply numbers without memorizing the whole multiplication table. We'll start with the method that can be used to do this problem by hand.

22 x 83 By Hand

So the first thing we will do is create two columns - one for halving 83 and the other for doubling 22. To do different numbers, just remember the larger number goes in the halving column and the smaller goes in the doubling column. Follow these steps to find your solution:

1. Divide all the numbers in the halving table by 2 until you reach 1

Halving | Doubling
|---83---|----22---|
|---41---|---------|
|---20---|---------|
|---10---|---------|
|---5----|---------|
|---2----|---------|
|---1----|---------|

1. Double all the numbers in the doubling column

Halving | Doubling
|---83---|----22---|
|---41---|----44---|
|---20---|----88---|
|---10---|---176---|
|---5----|---352---|
|---2----|---704---|
|---1----|--1408---|

1. Remove every row in the halving column that has an even answer

Halving | Doubling
|---83---|----22---|
|---41---|----44---|
|---5----|---352---|
|---1----|--1408---|

1. Now take the sum of all the answers in the doubling column for your answer!

22 + 44 + 352 + 1408 = 1826

You can check the answer with you calculator real quick:

22 * 83 = 1826

It works! Now why?

Rewriting in Powers of 2

Rewriting our doubling column in terms of 22 will help us see why this works and will explain our algorithm and also help us write it out in Python. So lets rewrite the doubling column as I said and excluding the even columns:

Halving | Doubling
|---83---|----22---|
|---41---|-22 x 2--|
|---5----|-22 x 16-|
|---1----|-22 x 64-|

Which we can rewrite in terms of to the power of 2:

22 x 2^0 + 22 x 2^2 + 22 x 2^4 + 22 x 2^6

Factor out the 22 and we get

22 x (2^0 + 2^2 + 2^4 + 2^6) = 22 x (1 + 4 + 16 + 64) = 22x83

22 x 83 is our original equation! So we find that the RPM is dependent on the fact that (2^0 + 2^2 + 2^4 + 2^6) = 83

We can do the same with the halving column and find similar results, but I'll let you do that at home!

The sum of the powers of two we just demonstrated is also called a binary expansion, which is important to us in computer science. 83 or (2^0 + 2^2 + 2^4 + 2^6) can be written in binary code as 1100101 where we put a 1 in each of the odd halving columns and a 0 in each of the even columns.

Well that was fun and a whole lot of unnecessary was put into writing that out by hand. Shall we implement this in Python now? I think we should.

Russian Peasant Multiplication in Python

# Set our variables 
n1 = 83
n2 = 22

halving = [n1]

import math

while(min(halving) > 1):
    halving.append(math.floor(min(halving)/2))

doubling = [n2]

while(len(doubling) < len(halving)):
    doubling.append(max(doubling) * 2)

import pandas as pd

half_double = pd.DataFrame(zip(halving, doubling))
half_double = half_double.loc[half_double[0]%2 == 1,:]
answer = sum(half_double.loc[:,1])

print(half_double)
print(answer)

And we get our answer printed out after running our program:

    0     1
0  83    22
1  41    44
4   5   352
6   1  1408

1826

There is your answer in Python!

Conclusion

This example may seem like it is kind of useless when you have a calculator right in front of you, but it really isn't. For one, it's a great way to figure out a multiplication problem without having to know the multiplication table. It also shows the deep connection between binary expansion and a way to multiply variables to get to an answer.

I hope you found this example interesting at the very least and I look forward to sharing the next cool algorithm - later!