Ancient Egyptian multiplication

The Russian peasant multiplication ( also Egyptian multiplication, Abessinische Bauer rule or doubling - halving method called ) is a simple method for multiplying two integers. Even in ancient times known, the procedure in Germany until well into modern times common to the Middle Ages and in Russia, from where the name originates.

It is certain that the Egyptians used a similar method for multiplication. The algorithm is described in the Rhind papyrus.

The method has the advantage that you only halve, double and add, in principle, be able to do, the basics is not needed. Implicitly written in binary multiplication is performed.

Method

Description

The method comprising the steps of:

The correctness of the Russian multiplication can be proved by induction.

Example

The product of 27 and 82 is calculated as follows:

Explanation

The Russian peasant multiplication can be followed by decomposition of the multiplier in powers of two:

The summands that contain the factor of zero, corresponding to the rows that will be deleted.

Comments

It can also calculate products of rational numbers by this method. This was also the Egyptians already known.

To minimize the number of division steps, it is advisable to exchange the factors if necessary.

To minimize the number of addition steps, it makes sense to swap the numbers so that the just factor is halved.

The same method: Binary exponentiation

The same idea can also be used to calculate powers with large integral exponents: The exponent is progressively halved and squared the base, at the end of the potencies were always multiplied with odd exponent. This process is called binary exponentiation.