Multiplication and division

Summary: Scholars throughout history have developed a variety of algorithms to compute multiplication and division.

Multiplication and division of numbers are useful for scaling a quantity, which is fundamental in any quantitative society. For example, to determine the correct cost for purchasing more than one unit of some item, the buyer should multiply the number of units by the unit price. One of the most common exposures people have to the concept of multiplication is the idea of repeated addition, which is frequently taught in elementary school. Some mathematicians object to this analogy, since it fails in specific instances, such as the case of fractions. Multiplication in this context can be thought of as a scaling process. Multiplication of mathematical objects is an operation that combines those objects in some representative manner. For example, matrix multiplication is the composition of the corresponding linear transformations.

Some theorize that the first evidence of multiplication is the Ishango Bone, a tool from Upper Paleolithic era, which may demonstrate multiplication by two. The ancient Chinese as early as the Warring States period (475–221 b.c.e.) developed a system of multiplication using a place-value system and counting boards for calculations. Multiplication using a place-value system of Hindu–Arabic numerals dates back to Indian mathematician and astronomer Brahmagupta in the seventh century.

Division is an operation that is generally the inverse of multiplication. For whole numbers, division can be thought of as finding the number of identically sized groups into which a number of individuals can be divided or partitioned. The remaining individuals, after all identically sized groups have been removed, are called the “remainder.” People in ancient Egypt commonly divided food and other supplies and formalized the notion of division. Concepts of division and multiplication are generalized and studied in the fields of number theory, algebra, and numerical analysis.

History of Multiplication Algorithms

One of the earliest methods for multiplying whole numbers is called the “Russian Peasant algorithm,” but a similar procedure was described thousands of years earlier in ancient Egyptian papyri and is based on doubling the multiplicand. Assume that an Egyptian scribe wanted to compute the product of 13 and 23. The scribe would compute the products 1×23=23, 2×23=46, 4×23=92, and 8×23=184. By doubling each previous result, the scribe would, realizing the sum of the multipliers 1, 4, and 8 equals the multiplier 13, find the sum 23+92+184=299, the required product. Thus, multiplication is reduced to being able to both double a number and add.

Another method used to multiply numbers is called “gelosia” or “lattice multiplication,” which is still taught in some elementary schools. This method probably originated in India before the twelfth century and eventually became the inspiration for Napier’s bones, an instrument created by John Napier, which was used to accomplish multiplication after its invention in the early 1600s. To multiply, for example, 23×48, one draws a 2-by-2 lattice of squares where each square is bisected by a diagonal from upper right to lower left. The rows are labeled, top to bottom, 4 and 8, while the columns are labeled, left to right, 2 and 3. The product of each of the single digits is written in the corresponding square as shown below. Once numbers in the lattice have been written, the final product, 1104, is formed by adding along the diagonals from upper right to lower left, being careful to remember to carry.

Another method still taught in the early twenty-first century has been called “cross-multiplication.” It was described by Leonardo Fibonacci in the twelfth century but was certainly known earlier in India and the Middle East. To multiply 23×48, one starts from the right and multiplies 3×8 to get 24. The 4 is written down and the 2 is remembered. Then the cross multiplication is performed, 2×8+3×4 to get 28, which is added to the remembered 2, obtaining 30. The 0 is written down and the 3 is remembered. Finally 2×4 is computed obtaining 8, which is added to the remembered 3, resulting in 11, which is written down. The final result is thus 1104. This method can be generalized and, by keeping various “remembered” digits using finger numbers, it is possible to multiply many two-digit numbers without writing down any intermediate results.

Probably the most popular method for multiplying that is taught in the early twenty-first century computes the products of multiplicand with each of the digits of the multiplier, working from right to left. Each of these successive products is shifted one more digit to the left. These partial products are then summed to obtain the final result as the following example shows:

This and similar methods were implemented on various counting boards, the abacus, and dust boards.

Division Algorithms

An ancient method for finding the quotient of two large whole numbers that is most appropriate for either the dust board or the Chinese counting board was adapted to pen and paper and became the “scratch method” that was used in Europe up into the nineteenth century. Two methods of computing long division using pencil and paper eventually replaced the scratch method.

One method is popular in Italy, England, and the United States and will be referred to as the “Italian method.” The other is popular in Spain, France, Latin America, Austria, and Germany. This second approach will be referred to as the “Spanish method.” Both methods date from at least the dawn of the sixteenth century. Both methods are shown by demonstrating how to find 2456/57, which is 43 with a remainder of 5.

In the Italian method, the dividend is written under a horizontal line above which the quotient will be written as it is found. The divisor is written to the left of the dividend with a vertical line drawn between them. It is determined that 57 will go into 245 at least (but no more than) 4 times, and 4—the first digit of the quotient—is written above the 5 of the dividend. The product 4×57=248 is computed and written below the 245. Subtraction is performed, obtaining 17 and the 6 from the dividend is brought down to the right of the 17. Then, it is determined that 57 will go into 176 at least (but no more than) 3 times. The product 3×57=171 is computed and subtracted from 176 to get the remainder of 5.

The Spanish method is cosmetically different and is characterized by many fewer digits being written down because the multiples 4×57=248 and 3×57=171 are never explicitly computed. To start, the dividend is written down followed by a long vertical line and the divisor. A horizontal line is then drawn under the dividend and divisor. The quotient will be developed to the right of the vertical line below the horizontal line one digit at a time. First, it is determined that the first digit of the quotient is 4. Then 4×7=28 is computed, which must be subtracted from 5. This operation cannot be done, and so a little 3 is written between the 4 and the 5 of the dividend. Now 28 can be subtracted from 35 obtaining 7, which is written under the 5 of the dividend. The 4×5 is found and added to the little 3 obtaining 23. This number is subtracted from 24 obtaining 1, which is written below the 4 of the dividend. To complete this phase, the 6 from the dividend is brought down so that the problem is now to divide 176 by 57. It is determined that 57 will go into 176 at least (but no more than) 3 times, and so 3 is written down as the next digit of the quotient. Computing 3×7=21, try to subtract 21 from 6, which cannot be done, and so a small 2 is written between the 7 and 6. Now, subtract 21 from 26, obtaining 5, which is written below the 6. Now, 3×5 is computed and added to the little 2, obtaining 17, which when subtracted from 17 is 0. As such, nothing needs to be written to the left of the 5. By the time a student is out of elementary school, it is expected that the annotations like the little 2 and 3 will no longer need to be written.

Checking Results

Because the algorithms for computing products and quotients of whole numbers are complex, methods to check the results have existed since antiquity. Since division and multiplication can be viewed as the inverse operations of each other, a division can be checked by multiplying the quotient by the divisor and adding the remainder. If the result is the dividend, then the division has been performed correctly. Another approach to checking the result of an arithmetic operation is to perform the operation using modular arithmetic, typically with respect to 7, 9, or 11. A number a modulo b is defined to be the remainder of a÷b. Thus, 267 modulo 9 is 6. There are easy tricks for computing numbers modulo 7, 9, and 11. For example, the method of “casting out 9s” can be used to compute 267 modulo 9 by simply summing the digits and subtracting 9 whenever the sum is over 9. For example, 2+6+7=15-9=6. In order to check the correctness of the multiplication 23×48=1104, check to see if [(23 modulo 9) × (48 modulo 9)] modulo 9 = 1104 modulo 9.

In this case, 5×3=15 and 15 modulo 9 is 6, which is equal 1104 modulo 9. One can conclude that the product, 1104, is probably correct. Although it is possible that such a check will confirm an incorrectly performed multiplication, this is unlikely.

Multiplication by Addition

Because multiplication and division are time consuming and tedious to perform compared to addition and subtraction, there has been much work to simplify the finding of products and quotients. Simplification results from using logarithms, invented in the seventeeth century, since

log(A × B) = log (A) + log(B).

Thus, it is easy to find the product of two numbers using a table of logarithms by looking up the logarithm of both the multiplier and the multiplicand in the table, adding these two logarithms and then using the table to find the number that has that sum as its logarithm.

It is also possible to convert multiplication to addition (and halving) using a table of cosines along with the trigonometric identity

This method was used by some astronomers before the invention of logarithms.

Rapid Multiplication and Division

Throughout history, people have developed the ability to multiply large digits in their head. Thomas Fuller, a slave, was one such person. For example, he calculated the number of seconds a man who is 70 years, 17 days, and 12 hours old has lived. He correctly answered 2,210,500,800 in only a minute and a half, and historians hypothesize that the algorithms he used were probably based on traditional African counting systems. In the twenty-first century, mathematician and magician Art Benjamin has turned his rapid mental calculations into educational entertainment.

Multiplication of whole numbers that can be represented as single binary words in a computer can typically be done with a single hardware instruction that combines addition and shifting to find the product. To multiply numbers with thousands of digits, other methods are possible that make use of fast methods for computing Fourier transforms, named for Joseph Fourier. The Schönhage–Strassen algorithm, developed by Arnold Schönhage and Volker Strassen, and the Fürer algorithm, developed by Martin Fürer, are two such methods. These complicated algorithms, however, have limited practicality when implemented on a conventional computer. Mathematicians in the field of numerical analysis consider issues of speed and error in computer algorithms.

Early computers multiplied or divided using repeated addition, subtraction, and shifting algorithms. Depending on the computing system, the amount of time required for multiplication or division on a computer is approximately the same. However, factoring a number into its unknown divisors is significantly harder. The RSA (which stands for the people who first described the system: R. Rivest, A. Shamir, and L. Adleman) cryptosystem takes advantage of this characteristic.

Generalizing Multiplication and Division

Multiplication and division can be used for computational purposes and to help understand other mathematical principles. The product of two rational numbers a/b and c/d is defined to be the rational number

whereas the quotient, a/b ÷ c/d is defined be the product of a/b and d/c. The reciprocal of a rational number, a/b, is the number b/a, since the product of a/b and a/b is 1. The product of two irrational numbers, which cannot be represented as a fraction of whole numbers, is approximated by taking the product of their approximating rational numbers. The product of irrational measurements can be found exactly with geometry using similar triangles.

Multiplication can be generalized to other mathematical objects, such as complex numbers and matrices. One of these objects, typically called the “identity” and denoted by “1,” has the property such that if a is any object, then the product of 1 and a is a. The reciprocal of an object a, if it exists, is denoted by a^-1 and is defined to the object so that the product, a×a^-1 is 1. When the reciprocal of an object b exists, then the quotient of objects a and b is defined to be a×b^-1.

Bibliography

Aho, A. V., J. E. Hopcrotf, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Reading, MA: Addison-Wesley, 1976.

Boyer, C. B. A History of Mathematics. Hoboken, NJ: John Wiley and Sons, 1991.

Gillings, R. J. Mathematics in the Time of the Pharaohs. New York: Dover Publications, 1982.

Smith, D. E. History of Mathematics, Volume II. New York: Dover Publications, 1958.