Ancient Egyptian multiplication In mathematics, ancient Egyptian multiplication (also known as Egyptian multiplication, Ethiopian multiplication, Russian multiplication, or peasant multiplication), one of two multiplication methods used by scribes, was a systematic method for multiplying two numbers that does not require the multiplication table, only the ability to multiply and divide by 2, and to add. It decomposes one of the multiplicands (generally the larger) into a sum of powers of two and creates a table of doublings of the second multiplicand. This method may be called mediation and duplation, where mediation means halving one number and duplation means doubling the other number. It is still used in some areas.
In the Russian peasant method, the powers of two in the decomposition of the multiplicand are found by writing it on the left and progressively halving the left column, discarding any remainder, until the value is 1 (or -1, in which case the eventual sum is negated), while doubling the right column as before. Lines with even numbers on the left column are struck out, and the remaining numbers on the right are added together.
Here i am describing two algorithms for the multiplication. The first one naive is a common loop way for finding the result of a * b
def naive(a,b): x = a; y = b z = 0 while x > 0 : z = z + y x = x – 1 return z
naive(4,5)
russian is an advanced algorithm to find a * b def russian(a,b): x = a; y = b z = 0 while x > 0: if x % 2 == 1 : z = z + y y = y <> 1 return z
russian ( 20, 7)
How russian method works :-
Make two columns. Write the two numbers you want to multiply at the top of each column.
20 | 7
Divide the number on the first column by 2 continually until you get to 1, writing every answer in the column. Ignore remainders.
20 | 7
10
5
2
1
Multiply the number in the second column by 2 until there are the same amount of numbers as there are in the first column.
20 | 7
10 | 14
5 | 28
2 | 56
1 | 112
For each even number in the first column cross out the number in the second column
20 | 7
10 | 14
5 | 28
2 | 56
1 | 112
Add the remaining numbers in the second column.
28 + 112 = 140 = 20 * 7
OR
x y z 20 7 0 10 14 0 5 28 0 z = z + y => z = 0 + 28 2 56 28 1 112 28 z = z + y => z = 28 + 112
So 20 * 7 = 0 + 28 + 112 = 140
And the Recursive algorithm is
def rec_russian(a ,b): if a == 0 : return 0 if a % 2 == 0 : return 2 rec_russian( a/2 ,b) //a is an even number return b + 2 rec_russian( (a-1)/2, b ) // a is an odd number so a-1 will be an even number. find (a-1)/2 * b by recusion and add b to it
When we compare both the algorithms it shows the naive is too slow compared to the russian method.
Ref: http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication