The
ancient Egyptians had laid out tables of a great number of powers of two, rather than recalculating them each time. To decompose a number, they identified 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.) After the decomposition of the first multiplicand, the person would 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. 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. Because mathematically speaking, multiplication of natural numbers is just "exponentiation in the additive
monoid", this multiplication method can also be recognised as a special case of the
Square and multiply algorithm for exponentiation.
Example 25 × 7 = ? Decomposition of the number 25: : The largest power of two is 16 and the second multiplicand is 7. As 25 = 16 + 8 + 1, the corresponding multiples of 7 are added to get 25 × 7 = 112 + 56 + 7 = 175. == Russian peasant multiplication ==