You are here

Russian Multiplication, Microprocessors, and Leibniz

Author(s): 
Sid Kolpas (Delaware County Community College)

You may have seen the method for multiplying two whole numbers together merely by halving the multiplier (ignoring the remainder), called mediation, and doubling the multiplicand, called duplation, so that all one has to do is divide and multiply by two. This method, called "Ethiopian multiplication" or "Russian multiplication" or sometimes "Russian peasant multiplication," is a popular topic in Liberal Arts Mathematics and Mathematics History classes. Another popular topic in Liberal Arts Mathematics classes is the binary number system. Interestingly, Russian multiplication is equivalent to the way microprocessors multiply using a binary algorithm, and therefore presages how modern-day computing devices multiply. Showing students the link between Russian multiplication and microprocessor multiplication gives them a deeper appreciation of electronic computing devices, as well as reviews for them the binary number system and introduces them to a computing algorithm. Moreover, it is an excellent topic with which to begin a discussion of the history of multiplication methods.

Ethiopian Priests and Russian Peasants

In the 1966 book, Excursions in Number Theory, the authors told the story of an Austrian colonel who wished to purchase seven bulls for 22 Maria Theresa (Austrian) dollars each in a village in a remote part of Ethiopia in the mid 1900s. In computing the bill, the "local priest" multiplied 7 bulls by $22 per bull using duplation and mediation (Ogilvy and Anderson, pp. 6-8). In commenting on this story, a later writer (Hayes, 2012) explained why he believed this method came to be called "Russian multiplication" in Europe (rather than, say, "Ethiopian multiplication," which is gaining favor today): 

The multiplicative system just demonstrated is very ancient indeed: it is probably the very earliest mathematical system worthy of the name and was doubtless invented, reinvented and forgotten innumerable times throughout human history. Since it does not require any form of writing and involves only three operations, pairing off, halving and doubling, which are both easy to carry out and are not troublesome conceptually, the system remained extremely popular with peasants the world over and became known as Russian Multiplication because, until recently, Russia was the European country with by far the largest proportion of innumerate and illiterate peasants.

Russian Multiplication

To multiply two whole numbers:

  1. Place each number at the top of side-by-side columns, with the multiplier in the left column and the multiplicand in the right column; because of the commutative property of multiplication, this could be reversed.
  2. In the multiplier column, keep dividing by two, omitting the remainder, until you reach 1.
  3. In the multiplicand column, keep doubling until 1 is reached in the multiplier column.
  4. Add the entries in the multiplicand column that are next to odd numbers in the multiplier column to get the product (these are starred in the following examples).

Example 1:  17 times 26

Multiplier Multiplicand
17* 26* (1 x 26)
8 52
4 104
2 208
1* 416* (16 X 26)                              
  26 + 416 = 442 = 1 x 26 + 16 x 26


Example 2:  16 times 35

Multiplier Multiplicand
16 35
8 70
4 140
2 280
1* 560* (16 x 35)
  560 = 16 x 35

The Binary Number System

The binary number system, long a practically useless example of an alternative number system, became vital to the success of present day digital computing devices. Fundamentally, these devices rely on the binary number system where 1 represents "on" and 0 represents "off". These l's and 0's are called bits. Arithmetic in binary becomes a task of bit manipulation. Following the properties of all number systems, the place values of the binary number system are powers of two, with digits 0 and 1. If you shift a binary number to the left (add a 0 on the right), you have multiplied it by 2. If you shift a binary number to the right (chop off the far right bit), you have divided it by 2, ignoring the remainder. Odd binary numbers end in 1; even binary numbers end in 0. Students might want to consider analogies for the decimal number system.

General Algorithm for Microprocessor Multiplication

The multiplier and multiplicand in a microprocessor are typically stored in binary form. To multiply two whole numbers, the general algorithm is as follows:

  1. Zero a running sum. That is, start a running sum at 0.
  2. If the right bit of the multiplier is 1, add the multiplicand to the running sum. This is equivalent in Russian multiplication to the instruction to "Add the entries in the multiplicand column that are next to odd numbers in the multiplier column to get the product." This is duplation.
  3. If the multiplier is 1, then we are done. The running sum contains the product.
  4. Shift the multiplier right 1 bit, chopping off the far right bit (thus dividing by 2, omitting the remainder). This is mediation.
  5. Shift the multiplicand left, adding a 0 on the right (thus multiplying by 2).
  6. Go back to step 2.

This algorithm is equivalent to Russian multiplication. The two previous examples will be used again to show that the two algorithms are equivalent.

Example 1:  17 times 26

Multiplier Multiplicand Running Sum
17 =100012* 26* (1 x 26) = 110102 0+26=26
8 = 10002 52 = 1101002 26
4 104 = 11010002 26
2 208 = 110100002 26
1* 416* (16 X 26) =1101000002          26  + 416 = 442
  26 + 416 = 442 = 1 x 26 + 16 x 26  


Example 2:  16 times 35

Multiplier Multiplicand Running Sum
16 35 = 1000112 0
8 70 = 10001102 0
4 140 = 100011002 0
2 280 = 1000110002 0
1* 560* (16 X 35) = 10001100002 0 + 560 = 560
  560 = 16 x 35  

It is simple for a microprocessor to shift binary numbers left and right and to add binary numbers.

In a Liberal Arts Mathematics class or Mathematics History class, showing that the algorithm for microprocessor multiplication and that for Russian multiplication are equivalent would be a good way to increase students’ interest and help them learn some history, study the binary number system, and gain insight into how digital devices multiply.

Leibniz and Binary Numbers

Gottfried Wilhelm Leibniz (1646-1716) studied binary numbers in 1679; his work appears in his article "Explication de l'Arithmétique Binaire," published in 1703. The full title in English is "Explanation of Binary Arithmetic, which uses only the characters 1 and 0, with some remarks on its usefulness, and on the light it throws on the ancient Chinese figures of Fu Xi." The article was republished in 1768 in Leibniz's Opera Omnia (Complete Works).

In the article, Leibniz interpreted the hexagrams of the I Ching as evidence of a binary calculus. As an admirer of Chinese culture, Leibniz was aware of the I Ching and noted how its hexagrams correspond to the binary numbers from 0 to 111111 (0 to 63). Leibniz was first introduced to the I Ching through his contact with the French Jesuit Joachim Bouvet, who visited China in 1685 as a missionary. Binary numerals were central to Leibniz's theology. He believed that binary numbers were symbolic of the Christian idea of creation (1) out of nothing (0). For an English translation of the article, see http://www.leibniz-translations.com/binary.htm.

The title page of the complete works (Opera Omnia) of Leibniz, published in Geneva in 1768 by Fratres de Tournes (Brothers of Tours), is shown below. In 1768, Louis Dutens (Ludovici Dutens) edited the first multi-volume edition of Leibniz's writings. Louis Dutens (1730–1812) was a French writer born in Tours. (All images below are of volumes from the author’s collection.)

Below: First page of Leibniz's article explaining binary arithmetic from his 1768 Opera Omnia. This article was originally published in 1703.

Leibniz explained the binary number system and binary arithmetic, providing examples of addition, subtraction, multiplication, and division:

Leibniz then provided some history of binary numbers:

Definition of Binary Arithmetic

In 1872, Charles Davies and William Peck published a Mathematical Dictionary and Cyclopedia of Mathematical Science. The title page is shown below. In their Cyclopedia, the authors' definition of Binary Arithmetic, shown just below, indicated that Leibniz perfected such a system, but that “it is rather curious than useful.” Little did they know what the future held for binary numbers!

 

References

Davies, Charles and William G. Peck. Cyclopedia of Mathematical Science. New York and Chicago: A.S. Barnes and Company, 1872.

Hayes, Sebastian, "Russian Peasant Mathematics," Origins of Mathematics, Jan. 26, 2012: https://originsofmathematics.com/2012/01/26/russian-peasant-multiplication/. Originally published in M500, Issue 243, School of Mathematics and Statistics, Open University.

Leibniz, Gottfried Wilhelm. Opera Omnia. Geneva: Fratres de Tournes, 1768.

Leibniz Translations .com website: http://www.leibniz-translations.com/binary.htm

Miller, Charles D., et al. Mathematical Ideas (thirteenth edition). Boston: Pearson, 2016.
Note: This is the text used for the Liberal Arts Mathematics course at the author’s college. It contains a lesson and exercises on "Russian peasant multiplication." It also contains a lesson on ancient Egyptian multiplication by doubling, which is related to the Russian multiplication algorithm described in this article.

Ogilvy, C. Stanley and John T. Anderson, Excursions in Number Theory, New York: Dover Publications, 1988 (original Oxford University Press, 1966).

Wikipedia. Binary Number: https://en.wikipedia.org/wiki/Binary_number

Sid Kolpas (Delaware County Community College), "Russian Multiplication, Microprocessors, and Leibniz," Convergence (March 2018), DOI:10.4169/convergence20180318

Dummy View - NOT TO BE DELETED