Other algorithms for long multiplication Lattice multiplication Russian Peasant multiplication Lattice multiplication The lattice method of multiplication appears in the first printed arithmetic book, printed in Treviso (Italy) in 1478. It shows this exact method and a variation as well as some variations of the long multiplication algorithm commonly taught today. Lattice multiplication and variations of today's standard long multiplication were introduced into Europe by Fibonacci (whose correct name is Leonardo of Pisa). He was an Italian who learnt the use of Arabic numerals from a Moorish teacher in North Africa. Before the Hindu-Arabic system was used in Europe, multiplication was often done with counters because Roman numerals were ill-suited to calculation and very few people knew how to multiply. The Hindu-Arabic system has made calculation fairly simple. In lattice multiplication, the partial products are laid out in a lattice and adding along the diagonals gives the answer to the multiplication. The lattice method of multiplication is illustrated by the following examples. Example 1 28 x 57 = 1596 As 28 and 57 have two digits each, a lattice is set out with two columns and two rows. The diagonals are drawn in each cell as shown below. 28 is written above the lattice with 2 above the first column and 8 above the second. 57 is written to the right of the lattice with 5 along the first row and 7 along the second. The partial products of these digits taken two at a time is set out in the corresponding cells with the tens above the diagonal and ones below. e.g. the partial products in this case are 5 x 8 (= 40), 5 x 2 (= 10), 7 x 8 (=56) and 7 x 2 (=14).These are set out as shown below. The sum along each diagonal is then recorded as shown below and these digits 1, 5, 9 and 6 form the answer to the multiplication. Thus 28 x 57 = 1596 Example 2 183 x 49 = 8967 The lattice set out for this multiplication will have 3 columns and two rows as 183 has 3 digits. As before the numbers are set out as shown below and the partial products are written down in their respective positions. The numbers along the diagonals are added to give the answer. Note that in this example adding along the third diagonal gives 19 which needs 1 to be carried to the diagonal above it. Therefore the addition should begin with the lowest diagonal ( the product of the ones from the two numbers). 183 x 49 = 8967  The Russian Peasant Algorithm This interesting algorithm of multiplication, which was used long ago, is based on the principle of doubling and halving. Its advantage is that it is only necessary to be able to double and halve numbers: you do not have to know your multiplication tables. Of the two numbers to be multiplied, one is halved and the other is doubled successively until the number in the halves column is reduced to 1. Remainders in halving odd numbers are ignored. The numbers in the doubles column corresponding to the odd numbers in the halves column are chosen and the rest are ignored. The sum of these selected numbers in the doubles column gives the product. The following examples illustrate the use of the algorithm. Example 1 28 x 57 = 1596 Two columns are set up as shown below, one for halves and the other for doubles. 28 is placed in the halves column and 57 in the doubles (They can be placed the other way round as well). Halves 28 Doubles 57 In the next step 28 is halved and 57 is doubled and written below the respective numbers. Halves 28 14 Doubles 57 114 Next 14 is halved to get 7 and 114 is doubled to give 228. This process is continued as shown below until the number in the halves column becomes 1. Note that remainders are ignored when halving odd numbers. Halves 28 14 7 3 1 Doubles 57 114 228 456 912 To work out the answer, amazingly the rows containing the even numbers in the halves column are now ignored. The remaining numbers in the halves column are 7, 3 and 1. The numbers in the doubles column corresponding to these, are added to give the product. 228 + 456 + 912 =1596 which is the product of 28 and 57. Example 2 183 x 49 = 8967 To use the Russian peasant algorithm, 49 is placed in the halves column and 183 in the doubles column. The halving and doubling process is represented below. Halves 49 24 12 6 3 1 Doubles 183 366 732 1464 2928 5856 The odd numbers in the halves column are 49, 3 and 1. The corresponding numbers in the doubles column are added to give the product. 183 + 2928 + 5856 = 8967. 183 x 49 = 8967 Why does it work? The method is simple enough to understand and most people who come across the method have no difficulty in doing it. However what surprises most people is why it works at all. While the principle of halving and doubling is logical and familiar enough. This method is simply ignores remainders and some of the rows. Here are some observations about the algorithm which help in seeing why it works. The method is compensatory in nature as with each subsequent step a factor 2 is moved from the number in the left column to the number in the right column. The numbers in the doubles column contain 1, 2, 4, 8, 16,... groups of the given number in the right column. In Example 1 the right hand column contains 1, 2, 4, 8 and 16 groups of 57. This shows a connection with the binary system of numeration. In example 1, the retained rows contain 4 groups, 8 groups and 16 groups of 57, giving 28 groups of 57 in all. In fact the retained lines correspond to the binary expansion of 28. This is the case with all examples and a little thought explains how it works. To construct a formal proof, think about the numbers in binary notation.