Ancient Egyptian multiplication: Information from Answers.com

Ancient Egyptian 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. Also known as Egyptian multiplication and Peasant multiplication, 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.

1 The decomposition
2 The table
3 The result
4 Example
5 Peasant multiplication
- 5.1 Proof
6 See also
7 External links

The decomposition

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.

Example:

1 x 2 = 2
2 x 2 = 4
4 x 2 = 8
8 x 2 = 16
16 x 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

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

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

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 13.

✔	1	238
	2	476
✔	4	952
✔	8	1904

	13	3094

Since 13 = 8 + 4 + 1, distribution of multiplication over addition gives 13 × 238 = (8 + 4 + 1) × 238 = 8 x 238 + 4 × 238 + 1 × 238 = 3094.

Peasant multiplication

Peasant multiplication, or Russian peasant multiplication, uses an algorithm similar to Egyptian multiplication.

Write the two numbers (A and B) you wish to multiply, each at the head of a column.
Starting with A, divide by 2, flooring the quotient, until there is nothing left to divide. Write the series of results under A.
Starting with B, keep doubling until you have doubled it as many times as you divided the first number. Write the series of results under B.
Add up all the numbers in the B-column that are next to an odd number in the A-column. This gives you the result.

Example: 27 times 82

A-column	B-column	Add this
27	82	82
13	164	164
6	328
3	656	656
1	1312	1312
		Result: 2214

The method works because multiplication is distributive, so:

$82 \times 27\,$	$= 82 \times (1\times 2^0 + 1\times 2^1 + 0\times 2^2 + 1\times 2^3 + 1\times 2^4\,)$
	$= 82 \times (1 + 2 + 8 + 16)\,$
	$= 82 + 164 + 656 + 1312\,$
	$= 2214\,.$

Proof

Peasant multiplication can be proven to be equivalent to the standard algorithm by mathematical induction:

Let $P M (n, m)$ denote the result of peasant multiplication for natural numbers $n$ and $m$ .

Base Case: For $n = 1$ and any $m \in \N$ it is true that: $PM(n, m) = PM(1, m) = 1 \cdot m = n \cdot m$ .

For

n = 2

and any $m \in \N$ it is true that : $PM(n, m) = PM(2, m) = 2 \cdot m = n \cdot m$ .

Inductive Step: Let $PM = n \cdot m$ for $PM \left ( \left \lfloor \frac n 2 \right \rfloor, 2m\right )$ . This is the induction hypothesis.

It is true that $PM(n, m) = PM \left (\left \lfloor \frac n 2 \right \rfloor, 2m \right ) + x$ , where $x = 0\!\,$ , if $n\!\,$ is even and $x = m\!\,$ , if $n\!\,$ is odd.

Because of the hypothesis from this follows $PM(n, m) = n \cdot m$ .

External links

Russian Peasant Multiplication
The Russian Peasant Algorithm (pdf file)
Peasant Multiplication from cut-the-knot
[1] New and Old classifications of Ahmes Papyrus
Egyptian Multiplication by Ken Caviness, The Wolfram Demonstrations Project.
Russian Peasant Multiplication at The Daily WTF

v • d • e Number-theoretic algorithms

Primality tests	AKS · APR · Ballie–PSW · ECPP · Fermat · Lucas · Lucas–Lehmer · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay–Strassen · Miller–Rabin · Trial division

Sieving algorithms	Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization

Integer factorization algorithms	CFRAC · Dixon's · ECM · Euler's · Pollard's rho · P − 1 · P + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's

Multiplication algorithms	Ancient Egyptian multiplication · Karatsuba algorithm · Toom–Cook multiplication · Schönhage–Strassen algorithm · Fürer's algorithm

Discrete logarithm algorithms	Baby-step giant-step · Pollard rho · Pollard kangaroo · Pohlig–Hellman · Index calculus · Function field sieve

GCD algorithms	Binary GCD · Euclidean · Extended Euclidean

Other algorithms	Aryabhata · Chakravala · integer relation algorithm · integer square root · Modular exponentiation · Schoof's · Shanks–Tonelli

Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	What were ancient egyptian role of agriculture in ancient egyptians? Read answer...
	Were the building of Ancient Egyptian homes influenced by Ancient Egyptian religion? Read answer...
	What were Ancient Egyptian merchants role in the Ancient Egyptian economy? Read answer...

	Which not true The ancient Egyptians knew the importance of cleanliness The ancient Egyptians knew the importance of chemotherapy The ancient Egyptians knew the importance of convalescence?
	How is ancient Egyptian time written?
	What was the ancient egyptians civilization theaters?

Ancient Egyptian multiplication

Contents