Ancient Egyptian multiplication

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.

The second Egyptian multiplication and division technique was known from the hieratic Moscow and Rhind Mathematical Papyri written in the seventeenth century B.C. by the scribe Ahmes.

Although in ancient Egypt the concept of base 2 did not exist, the algorithm is essentially the same algorithm as long multiplication after the multiplier and multiplicand are converted to binary. The method as interpreted by conversion to binary is therefore still in wide use today as implemented by binary multiplier circuits in modern computer processors.

The decomposition[edit]

The decomposition into a sum of powers of two was not intended as a change from base ten to base two; the Egyptians then were unaware of such concepts and had to resort to much simpler methods. The ancient Egyptians had laid out tables of a great number of powers of two so as not to be obliged to recalculate them each time. The decomposition of a number thus consists of finding the powers of two which make it up. The Egyptians knew empirically that a given power of two would only appear once in a number. For the decomposition, they proceeded methodically; they would initially find the largest power of two less than or equal to the number in question, subtract it out and repeat until nothing remained. (The Egyptians did not make use of the number zero in mathematics.)

To find the largest power of 2 keep doubling your answer starting with number 1, for example

1 × 2 = 2
2 × 2 = 4
4 × 2 = 8
8 × 2 = 16
16 × 2 = 32

Example of the decomposition of the number 25:

The largest power of two less than or equal to 25 is 16: 25 – 16 = 9
The largest power of two less than or equal to 9 is 8: 9 – 8 = 1
The largest power of two less than or equal to 1 is 1: 1 – 1 = 0
25 is thus the sum of the powers of two: 16, 8 and 1.

The table[edit]

After the decomposition of the first multiplicand, it is necessary to construct a table of powers of two times the second multiplicand (generally the smaller) from one up to the largest power of two found during the decomposition. In the table, a line is obtained by multiplying the preceding line by two.

For example, if the largest power of two found during the decomposition is 16, and the second multiplicand is 7, the table is created as follows:

1 7
2 14
4 28
8 56
16 112

The result[edit]

The result is obtained by adding the numbers from the second column for which the corresponding power of two makes up part of the decomposition of the first multiplicand.

The main advantage of this technique is that it makes use of only addition, subtraction, and multiplication by two.

Example[edit]

Here, in actual figures, is how 238 is multiplied by 13. The lines are multiplied by two, from one to the next. A check mark is placed by the powers of two in the decomposition of 238.

1 13
2 26
4 52
8 104
16 208
32 416
64 832
128 1664

238 3094

Since 238 = 2 + 4 + 8 + 32 + 64 + 128, distribution of multiplication over addition gives:

238 × 13 = (128 + 64 + 32 + 8 + 4 + 2) × 13
= 128 × 13 + 64 × 13 + 32 × 13 + 8 × 13 + 4 × 13 + 2 × 13
= 1664 + 832 + 416 + 104 + 52 + 26
= 3094

Russian peasant multiplication[edit]

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.[1]

For example, to multiply 238 by 13, the smaller of the numbers (to reduce the number of steps), 13, is written on the left and the larger on the right. The left number is progressively halved (discarding any remainder) and the right one doubled, until the left number is 1:
 13  238
 6  (remainder discarded) 476
 3  952
 1  (remainder discarded) 1904
Lines with even numbers on the left column are struck out, and the remaining numbers on the right are added, giving the answer as 3094:
 13   238 
 6   476 
 3   952 
 1  1904 

 3094 
The algorithm can be illustrated with the binary representation of the numbers:
1101 (13) 11101110 (238)
110 (6) 111011100 (476)
11 (3) 1110111000 (952)
1 (1) 11101110000 (1904)
       
1 1 1 0 1 1 1 0 (238)
× 1 1 0 1 (13)

1 1 1 0 1 1 1 0 (238)
0 0 0 0 0 0 0 0 0 (0)
1 1 1 0 1 1 1 0 0 0 (952)
+ 1 1 1 0 1 1 1 0 0 0 0 (1904)

1 1 0 0 0 0 0 1 0 1 1 0 (3094)

See also[edit]

References[edit]

  1. ^ Cut the Knot - Peasant Multiplication

External links[edit]