Editing Multiplication algorithm (section)

==Algorithms for multiplying by hand==

In addition to the standard long multiplication, there are several other methods used to perform multiplication by hand. Such algorithms may be devised for speed, ease of calculation, or educational value, particularly when computers or [[multiplication table]]s are unavailable.

===Grid method===
{{main|Grid method multiplication}}
The [[grid method multiplication|grid method]] (or box method) is an introductory method for multiple-digit multiplication that is often taught to pupils at [[primary school]] or [[elementary school]].  It has been a standard part of the national primary school mathematics curriculum in England and Wales since the late 1990s.<ref>{{cite news |first=Gary |last=Eason |url=http://news.bbc.co.uk/1/hi/education/639937.stm |title=Back to school for parents |publisher=[[BBC News]] |date=13 February 2000}}<br>{{cite news |first=Rob |last=Eastaway |author-link=Rob Eastaway |url=https://www.bbc.co.uk/news/magazine-11258175 |title=Why parents can't do maths today |publisher=BBC News |date=10 September 2010}}</ref>

Both factors are broken up ("partitioned") into their hundreds, tens and units parts, and the products of the parts are then calculated explicitly in a relatively simple multiplication-only stage, before these contributions are then totalled to give the final answer in a separate addition stage.

The calculation 34 × 13, for example, could be computed using the grid:
<div style="float:right">
<pre>  300
   40
   90
 + 12
 ————
  442</pre></div>
{| class="wikitable" style="text-align: center;"
! width="40" scope="col" | ×
! width="40" scope="col" | 30
! width="40" scope="col" | 4
|-
! scope="row" | 10
|300
|40
|-
! scope="row" | 3
|90
|12
|}

followed by addition to obtain 442, either in a single sum (see right), or through forming the row-by-row totals 
: (300 + 40) + (90 + 12) = 340 + 102 = 442.

This calculation approach (though not necessarily with the explicit grid arrangement) is also known as the [[partial products algorithm]].  Its essence is the calculation of the simple multiplications separately, with all addition being left to the final gathering-up stage.

The grid method can in principle be applied to factors of any size, although the number of sub-products becomes cumbersome as the number of digits increases. Nevertheless, it is seen as a usefully explicit method to introduce the idea of multiple-digit multiplications; and, in an age when most multiplication calculations are done using a calculator or a spreadsheet, it may in practice be the only multiplication algorithm that some students will ever need.

===Lattice multiplication===
{{main|Lattice multiplication}}
[[File:Hindu lattice.svg|thumb|right|First, set up the grid by marking its rows and columns with the numbers to be multiplied. Then, fill in the boxes with tens digits in the top triangles and units digits on the bottom.]]
[[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 is algorithmically equivalent to long multiplication. 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]]. Fibonacci 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>{{cite journal |last1=Corlu |first1=M.S. |last2=Burlbaw |first2=L.M. |last3=Capraro |first3=R.M. |last4=Corlu |first4=M.A. |last5=Han |first5=S. |title=The Ottoman Palace School Enderun and the Man with Multiple Talents, Matrakçı Nasuh |journal=Journal of the Korea Society of Mathematical Education Series D: Research in Mathematical Education |volume=14 |issue=1 |pages=19–31 |date=2010 |doi= |url=https://koreascience.kr/article/JAKO201017337333137.page}}</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.{{citation needed|date=January 2016}}

*During the multiplication phase, the lattice is filled in with two-digit products of the corresponding digits labeling each row and column: the tens digit goes in the top-left corner.
*During the addition phase, the lattice is summed on the diagonals.
* Finally, if a carry phase is necessary, the answer as shown along the left and bottom sides of the lattice is converted to normal form by carrying ten's digits as in long addition or multiplication.

====Example====
The pictures on the right show how to calculate 345 × 12 using lattice multiplication. As a more complicated example, consider the picture below displaying the computation of 23,958,233 multiplied by 5,830 (multiplier); the result is 139,676,498,390.  Notice 23,958,233 is along the top of the lattice and 5,830 is along the right side.  The products fill the lattice and the sum of those products (on the diagonal) are along the left and bottom sides.  Then those sums are totaled as shown.
{|
| rowspan="2" |
<pre>
     2   3   9   5   8   2   3   3
   +---+---+---+---+---+---+---+---+-
   |1 /|1 /|4 /|2 /|4 /|1 /|1 /|1 /|
   | / | / | / | / | / | / | / | / | 5
 01|/ 0|/ 5|/ 5|/ 5|/ 0|/ 0|/ 5|/ 5|
   +---+---+---+---+---+---+---+---+-
   |1 /|2 /|7 /|4 /|6 /|1 /|2 /|2 /|
   | / | / | / | / | / | / | / | / | 8
 02|/ 6|/ 4|/ 2|/ 0|/ 4|/ 6|/ 4|/ 4|
   +---+---+---+---+---+---+---+---+-
   |0 /|0 /|2 /|1 /|2 /|0 /|0 /|0 /|
   | / | / | / | / | / | / | / | / | 3
 17|/ 6|/ 9|/ 7|/ 5|/ 4|/ 6|/ 9|/ 9|
   +---+---+---+---+---+---+---+---+-
   |0 /|0 /|0 /|0 /|0 /|0 /|0 /|0 /|
   | / | / | / | / | / | / | / | / | 0
 24|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|
   +---+---+---+---+---+---+---+---+-
     26  15  13  18  17  13  09  00</pre>
||
<pre>
 01
 002
 0017
 00024
 000026
 0000015
 00000013
 000000018
 0000000017
 00000000013
 000000000009
 0000000000000
 —————————————
  139676498390
</pre>
|-
||
 = 139,676,498,390
|}

===Russian peasant multiplication===
{{Main|Peasant multiplication}}
The binary method is also known as peasant multiplication, because it has been widely used by people who are classified as peasants and thus have not memorized the [[multiplication table]]s required for long multiplication.<ref>{{Cite web|url=https://www.cut-the-knot.org/Curriculum/Algebra/PeasantMultiplication.shtml|title=Peasant Multiplication|author-link=Alexander Bogomolny|last=Bogomolny|first= Alexander |website=www.cut-the-knot.org|access-date=2017-11-04}}</ref>{{failed verification|date=March 2020}} The algorithm was in use in ancient Egypt.<ref>{{Cite book |first=D. |last=Wells | author-link=David G. Wells | year=1987 |page=44 |title=The Penguin Dictionary of Curious and Interesting Numbers |publisher=Penguin Books |isbn=978-0-14-008029-2}}</ref> Its main advantages are that it can be taught quickly, requires no memorization, and can be performed using tokens, such as [[poker chips]], if paper and pencil aren't available. The disadvantage is that it takes more steps than long multiplication, so it can be unwieldy for large numbers.

====Description====
On paper, write down in one column the numbers you get when you repeatedly halve the multiplier, ignoring the remainder; in a column beside it repeatedly double the multiplicand. Cross out each row in which the last digit of the first number is even, and add the remaining numbers in the second column to obtain the product.

====Examples====
This example uses peasant multiplication to multiply 11 by 3 to arrive at a result of 33.

 Decimal:     Binary:
 11   3       1011  11
 5    6       101  110
 2   <s>12</s>       10  <s>1100</s>
 1   24       1  11000
     ——         ——————
     33         100001

Describing the steps explicitly:

* 11 and 3 are written at the top
* 11 is halved (5.5) and 3 is doubled (6).  The fractional portion is discarded (5.5 becomes 5).
* 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 are summed: 3 + 6 + 24 = 33.

The method works because multiplication is [[distributivity|distributive]], so:

: <math>
\begin{align}
3 \times 11 & = 3 \times (1\times 2^0 + 1\times 2^1 + 0\times 2^2 + 1\times 2^3) \\
& = 3 \times (1 + 2 + 8) \\
& = 3 + 6 + 24 \\
& = 33.
\end{align}
</math>

A more complicated example, using the figures from the earlier examples (23,958,233 and 5,830):

 Decimal:             Binary:
 5830  <s>23958233</s>       1011011000110  <s>1011011011001001011011001</s>
 2915  47916466       101101100011  10110110110010010110110010
 1457  95832932       10110110001  101101101100100101101100100
 728  <s>191665864</s>       1011011000  <s>1011011011001001011011001000</s>
 364  <s>383331728</s>       101101100  <s>10110110110010010110110010000</s>
 182  <s>766663456</s>       10110110  <s>101101101100100101101100100000</s>
 91  1533326912       1011011  1011011011001001011011001000000
 45  3066653824       101101  10110110110010010110110010000000
 22  <s>6133307648</s>       10110  <s>101101101100100101101100100000000</s>
 11 12266615296       1011  1011011011001001011011001000000000
 5  24533230592       101  10110110110010010110110010000000000
 2  <s>49066461184</s>       10  <s>101101101100100101101100100000000000</s>
 1  98132922368       1  <u>1011011011001001011011001000000000000</u>
   ————————————          1022143253354344244353353243222210110 (before carry)
   139676498390         10000010000101010111100011100111010110

===Quarter square multiplication===

This formula can in some cases be used, to make multiplication tasks easier to complete:

: <math>
 \frac{\left(x+y\right)^2}{4}  -  \frac{\left(x-y\right)^2}{4} =
\frac{1}{4}\left(\left(x^2+2xy+y^2\right) - \left(x^2-2xy+y^2\right)\right) =
\frac{1}{4}\left(4xy\right) = xy.
</math>

In the case where <math>x</math> and <math>y</math> are integers, we have that
:<math> (x+y)^2 \equiv (x-y)^2 \bmod 4</math>
because <math>x+y</math> and <math>x-y</math> are either both even or both odd. This means that
:<math>\begin{align}
xy &= \frac14(x+y)^2 - \frac14(x-y)^2 \\
   &= \left((x+y)^2 \text{ div } 4\right)- \left((x-y)^2 \text{ div } 4\right)
\end{align}</math>
and it's sufficient to (pre-)compute the integral part of squares divided by 4 like in the following example.

====Examples ====
Below is a lookup table of quarter squares with the remainder discarded for the digits 0 through 18; this allows for the multiplication of numbers up to {{math|9×9}}.

{| border="1" cellspacing="0" cellpadding="3" style="margin:0 0 0 0.5em; background:#fff; border-collapse:collapse; border-color:#7070090;" class="wikitable"
|- style="text-align:right;"
|{{math|''n''}}&nbsp;&nbsp; || &nbsp;&nbsp;0 || &nbsp;&nbsp;1 || &nbsp;&nbsp;2 || &nbsp;&nbsp;3 || &nbsp;&nbsp;4 || &nbsp;&nbsp;5 || &nbsp;&nbsp;6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16 || 17 || 18
|- style="text-align:right;"
|{{math|⌊''n''<sup>2</sup>/4⌋}} || 0 || 0 || 1 || 2 || 4 || 6 || 9 || 12 || 16 || 20 || 25 || 30 || 36 || 42 || 49 || 56 || 64 || 72 || 81
|}

If, for example, you wanted to multiply 9 by 3, you observe that the sum and difference are 12 and 6 respectively. Looking both those values up on the table yields 36 and 9, the difference of which is 27, which is the product of 9 and 3.

====History of quarter square multiplication====

In prehistoric time, quarter square multiplication involved [[Floor and ceiling functions|floor function]];  that some sources<ref>{{citation |title= Quarter Tables Revisited: Earlier Tables, Division of Labor in Table Construction, and Later Implementations in Analog Computers |last=McFarland |first=David|url=http://escholarship.org/uc/item/5n31064n |page=1 |year=2007}}</ref><ref>{{cite book| title=Mathematics in Ancient Iraq: A Social History |last=Robson |first=Eleanor |page=227 |year=2008 |publisher=Princeton University Press |isbn= 978-0691201405 }}</ref> attribute to [[Babylonian mathematics]] (2000–1600 BC).

Antoine Voisin published a table of quarter squares from 1 to 1000 in 1817 as an aid in multiplication. A larger table of quarter squares from 1 to 100000 was published by Samuel Laundy in 1856,<ref>{{Citation |title=Reviews |journal=The Civil Engineer and Architect's Journal |year=1857 |pages=54–55 |url=https://books.google.com/books?id=gcNAAAAAcAAJ&pg=PA54 |postscript=.}}</ref> and a table from 1 to 200000 by Joseph Blater in 1888.<ref>{{Citation|title=Multiplying with quarter squares |first=Neville |last=Holmes| journal=The Mathematical Gazette |volume=87 |issue=509 |year=2003 |pages=296–299 |jstor=3621048|postscript=.|doi=10.1017/S0025557200172778 |s2cid=125040256 }}</ref>

Quarter square multipliers were used in [[analog computer]]s to form an [[analog signal]] that was the product of two analog input signals. In this application, the sum and difference of two input [[voltage]]s are formed using [[operational amplifier]]s. The square of each of these is approximated using [[piecewise linear function|piecewise linear]] circuits. Finally the difference of the two squares is formed and scaled by a factor of one fourth using yet another operational amplifier.

In 1980, Everett L. Johnson proposed using the quarter square method in a [[Digital data|digital]] multiplier.<ref name=eljohnson>{{Citation |last = Everett L. |first = Johnson |date = March 1980 |title = A Digital Quarter Square Multiplier |periodical = IEEE Transactions on Computers |location = Washington, DC, USA |publisher = IEEE Computer Society |volume = C-29 |issue = 3 |pages = 258–261 |issn = 0018-9340 |doi =10.1109/TC.1980.1675558 |s2cid = 24813486 }}</ref> To form the product of two 8-bit integers, for example, the digital device forms the sum and difference, looks both quantities up in a table of squares, takes the difference of the results, and divides by four by shifting two bits to the right. For 8-bit integers the table of quarter squares will have 2<sup>9</sup>&minus;1=511 entries (one entry for the full range 0..510 of possible sums, the differences using only the first 256 entries in range 0..255) or 2<sup>9</sup>&minus;1=511 entries (using for negative differences the technique of 2-complements and 9-bit masking, which avoids testing the sign of differences), each entry being 16-bit wide (the entry values are from (0²/4)=0 to (510²/4)=65025).

The quarter square multiplier technique has benefited 8-bit systems that do not have any support for a hardware multiplier. Charles Putney implemented this for the [[MOS Technology 6502|6502]].<ref name=cputney>{{Cite journal  |last = Putney |first = Charles |title = Fastest 6502 Multiplication Yet|date = March 1986 |journal = Apple Assembly Line |volume = 6 |issue = 6 |url = http://www.txbobsc.com/aal/1986/aal8603.html#a5}}</ref>