Egyptian MultiplicationThe ancient Egyptians used a curious way to multiply two numbers. The algorithm draws on thebinary system: multiplication by 2, or just adding a number two itself. Unlike, the Russian Peasant Multiplication that determines the involved powers of 2 automatically, the Egyptian algorithm has an extra step where those powers have to be found explicitly. The applet below allows for experimentation with the algorithm I’ll present shortly. The two blue numbers at the top – the multiplicands – can be modified by clicking on their digits. (The digits can be treated individually or as part of a number depending on the state of the “Autonomous digits” checkbox.) The number of digits in the multiplicands changes from 1 through 4.
Write two multiplicands with some room in-between as the captions for two columns of numbers. The first column starts with 1 and the second with the second multiplicand. Below, in each column, write successively the doubles of the preceding numbers. The first column will generate the sequence of the powers of 2: 1, 2, 4, 8, … Stop when the next power becomes greater than the first multiplicand. I’ll use the same example as in the Russian Peasant Multiplication, 85×18:
The right column is exactly the same as it would be in the Russian Peasant Multiplication. The left column consists of the powers of two. The red ones are important: the corresponding entries in the right column add up to the product 85×18 = 1530: Why some powers of two come in red, while others in gold? Those in red add up to the first multiplicand:
which corresponds to the binary representation of 85:
According to the Rhind papyrus these powers are found the following way. 64 is included simply because it’s the largest power below 85. Compute 85 – 64 = 21 and find the largest power of 2 below 21: 16. Compute 21 – 16 = 5 and find the largest power of 2 below 5: 4. Compute 5 – 4 = 1 and observe that the result, 1, is a power of 2: 1 = 2 For the product 18×85, we get the following result: It is also called as Russian peasant Algorithm. Now let us deal this problem in python first prepare imports ```
from __future__ import division
import math
```
we can design a function that returns the greatest power of 2 which is less than or equal to the given no.Because we need to frequently use that concept. ```
def greatest2power(n,i=0):
while int(math.pow(2,i)) <= n : i = i+1
return int(math.pow(2,i-1))
```
Now let us take inputs.a multiplier, and a multiplicand. ```
m = int(raw_input('Enter multiplicand'))
n = int(raw_input('Enter multiplier'))
```
Now according to the above description,Set greatest to first,and least to second. ```
if m>n : first , second = m , n
else : first , second = n , m
```
We are simulating two columns for 85 and 18 with fcol,scol.Seed is the two multiple which is used to populate those columns according to the algorithm. ```
fcol , scol = [] , []
seed = 1
```
Now we are populating the two columns with the values generated as algorithm described.Code snippet below is quite obvious. ```
while seed <= greatest2power(first):
fcol.append(seed)
scol.append(second*seed)
seed = seed*2
```
Now we need to compute the valid powers of two which are subtracting from the first element and store them in a list. ```
valid , backseed = [] , seed//2
while backseed>=1:
valid.append(backseed)
temp = backseed
backseed = greatest2power(first-backseed)
first = first - temp
```
The above snippet is analogous to (85-64=21, 21>16) and (21-16=5,5>4), (5-4=1>=1).so [64,16,4,1] are the valid powers of 2. Now we iterate over that zip of fcol , scol in order to fetch the corresponding element for a valid two power. ```
answer = 0
for sol in valid:
for a,b in zip(fcol,scol):
if a==sol:
answer = answer+b
```
Finally we got the answer stored in answer variable.we are printing it. ```
print 'The Egyptian Product is:%d'%answer
```
What is the specialty in this?.Instead we can do straight forward multiplication.The actual beauty lies in the Egyptian strategy was they used only 2 in their calculation.If you see in the program raising a 2 power is equivalent of adding 2 extra to it.So Egyptians did multiplications with addition operator and number 2 as we did in program.Here goes the complete code here. https://drive.google.com/file/d/0B6VAvV8caRaBd1JDQU5tendBVVE/view?usp=sharing resources : http://www.cut-the-knot.org/Curriculum/Algebra/EgyptianMultiplication.shtml http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication |