Russian pawn multiplication

The Russian pawn multiplication (also called Egyptian multiplication , Abyssinian pawn rule or doubling-halving method ) is a simple procedure for multiplying two natural numbers . Known in antiquity , the process was common in Germany well into the Middle Ages and in Russia well into modern times , which is where the name comes from.

It is certain that the Egyptians already used an analogous method for multiplication. The algorithm is described on the Rhind papyrus .

The method has the advantage that in principle you only have to be able to halve, double and add , the multiplication table is not required. A written multiplication is implicitly carried out in the binary system .

Procedure

description

The procedure consists of the following steps:

You write the two numbers to be multiplied side by side.
On the left side (multiplier) the numbers are halved (remainders rounded down) and the results are written one below the other until you get to 1.
On the right side (multiplicand) the numbers are doubled and written one below the other.
The numbers on the right (doubled) are deleted if the number on the left is even.
The sum of the numbers on the right that are not crossed out gives the product you are looking for.

The correctness of the Russian multiplication can be proven by complete induction .

example

The product of 27 and 82 is calculated as follows:

multiplier	multiplicand	to add up
27	82	82
13	164	164
6th	328	~~328~~
3	656	656
1	1312	1312
Product:		2214

Explanation

The Russian pawn multiplication can be understood by dividing the multiplier into powers of two:

${\ displaystyle {\ begin {matrix} 82 \ times 27 & = & 82 \ times (2 ^ {0} + 2 ^ {1} +0 \ times 2 ^ {2} + 2 ^ {3} + 2 ^ {4} ) \\\ & = & 82 \ times 2 ^ {0} +82 \ times 2 ^ {1} +82 \ times 0 + 82 \ times 2 ^ {3} +82 \ times 2 ^ {4} \\\ & = & 82 + 164 + 0 + 656 + 1312 \\\ & = & 2214 \ end {matrix}}}$

The summands that contain the factor zero correspond to the lines that are deleted.

Remarks

This method can also be used to calculate products of rational numbers. This was also known to the Egyptians.

In order to minimize the number of division steps, it is advisable to swap the factors if necessary.

To minimize the number of addition steps, it is advisable to swap the numbers so that the even factor is halved.

Analogous procedure: binary exponentiation

The same idea can also be used to calculate powers with large integer exponents: the exponent is gradually halved and the base squared, at the end the powers are multiplied with odd exponents. This procedure is called binary exponentiation .

literature

Otto Forster: Algorithmic Number Theory . 2nd Edition. Springer Fachmedien, Wiesbaden 2015, ISBN 978-3-658-06539-3 . , Chapter 2, section " The Russian Peasant Rule of Multiplication. "
Jens Gallenbacher: Adventure Computer Science . 4th edition. Springer-Verlag, 2017, ISBN 978-3-662-53964-4 . , Chapter 5, section " The Ethiopian Multiplication. "

Web links

Eric W. Weisstein : Russian Multiplication . In: MathWorld (English). and in tungsten Demonstration Project (Engl.)

Individual evidence

^ Hans Wußing : 6000 years of mathematics. A cultural and historical journey through time. From the beginning to Leibniz and Newton . Springer, Berlin 2008, ISBN 978-3-540-77189-0 , pp. 116 .
↑ James Newman: The World of Mathematics. Volume 1, Simon & Schuster, New York 1956, p. 170.
↑ James Newman: The World of Mathematics. Volume 1, New York 1956, p. 173.

[1] Hans Wußing : 6000 years of mathematics. A cultural and historical journey through time. From the beginning to Leibniz and Newton . Springer, Berlin 2008, ISBN 978-3-540-77189-0 , pp. 116 .

[2] James Newman: The World of Mathematics. Volume 1, Simon & Schuster, New York 1956, p. 170.

[3] James Newman: The World of Mathematics. Volume 1, New York 1956, p. 173.