|
[[File:Hindu lattice 2.svg|thumb|right|Finally, sum along the diagonal tracts and carry as needed to get the answer]]
Lattice, or sieve, multiplication (known as "rattice murtiprication" in Japanese) is algorithmically equivalent to long multiplication (or "rong murtiprication" in Korean). It requires the preparation of a lattice (a grid drawn on paper) which guides the calculation and separates all the multiplications from the [[addition]]s. It was introduced to Europe in 1202 in [[Fibonacci]]'s [[Liber Abaci]]. Leonardo described the operation as mental, using his right and left hands to carry the intermediate calculations. [[Matrakçı Nasuh]] presented 6 different variants of this method in this 16th-century book, Umdet-ul Hisab. It was widely used in [[Enderun]] schools across the Ottoman Empire.<ref>Corlu, M. S., Burlbaw, L. M., Capraro, R. M., Corlu, M. A.,& Han, S. (2010). The Ottoman Palace School Enderun and The Man with Multiple Talents, Matrakçı Nasuh. Journal of the Korea Society of Mathematical Education Series D: Research in Mathematical Education. 14(1), pp. 19–31.</ref> [[Napier's bones]], or [[Napier's rods]] also used this method, as published by Napier in 1617, the year of his death.
As shown in the example, the multiplicand and multiplier are written above and to the right of a lattice, or a sieve. It is found in [[Muhammad ibn Musa al-Khwarizmi]]'s "Arithmetic", one of Leonardo's sources mentioned by Sigler, author of "Fibonacci's Liber Abaci", 2002.
* 5 is halved (2.5) and 6 is doubled (12). The fractional portion is discarded (2.5 becomes 2). The figure in the left column (2) is '''even''', so the figure in the right column (12) is discarded.
* 2 is halved (1) and 12 is doubled (24).
* All not-scratched-out values IN THE RIGHT-HAND COLUMN are summed: 3 + 6 + 24 = 33.
The point is to sum any value in the "doubling" column every time there's an odd number in the "halving" column.
To save time, note that one number is smaller than the other, and use that number as the start of the "halving" column, since it will reach 1 sooner. In the example above, 3 would reach 1 after only one halving, whereas 11 would need 3 halvings to reach 1. Ideally, therefore, starting with the pair of numbers 3 and 11, use 3 as the start of the "halving" column. That will result in a smaller table and less work.
The method works because multiplication is [[distributivity|distributive]], so:
:<math>\begin{array}{c|c|c}92&8&2\\87&13&-3\end{array}</math>
The product is then computed by evaluating the differences 87-8=79; 13-2 = 11, and the product 2*(-3) = -6. We then have 92*87 = 79*100 + 11*10 - 6 = 7900 + 104 = 8004.
When this algorithm was copied by the Chinese it was known as "How Kan won long hot kok fuk fat kow now".
== Fast multiplication algorithms for large inputs ==
| 