Editing Multiplication (section)

==Computation==
{{Main|Multiplication algorithm}}
[[file:צעצוע מכני משנת 1918 לחישובי לוח הכפל The Educated Monkey.jpg|upright|right|thumb|The Educated Monkey—a [[tin toy]] dated 1918, used as a multiplication "calculator". <small>For example: set the monkey's feet to 4 and 9, and get the product—36—in its hands.</small>]]

Many common methods for multiplying numbers using pencil and paper require a [[multiplication table]] of memorized or consulted products of small numbers (typically any two numbers from 0 to 9). However, one method, the [[Ancient Egyptian multiplication|peasant multiplication]] algorithm, does not. The example below illustrates "long multiplication" (the "standard algorithm", "grade-school multiplication"):

       23958233
 ×         5830
 ———————————————
       00000000 ( =      23,958,233 ×     0)
      71874699  ( =      23,958,233 ×    30)
    191665864   ( =      23,958,233 ×   800)
 + 119791165    ( =      23,958,233 × 5,000)
 ———————————————
   139676498390 ( = 139,676,498,390        )
In some countries such as [[Germany]], the multiplication above is depicted similarly but with the original problem written on a single line and computation starting with the first digit of the multiplier:<ref>{{Cite web |title=Multiplication |url=http://www.mathematische-basteleien.de/multiplication.htm |access-date=2022-03-15 |website=mathematische-basteleien.de}}</ref>
 23958233 · 5830
 ———————————————
    119791165
     191665864
       71874699
        00000000 
 ———————————————
    139676498390
Multiplying numbers to more than a couple of decimal places by hand is tedious and error-prone. [[Common logarithm]]s were invented to simplify such calculations, since adding logarithms is equivalent to multiplying. The [[slide rule]] allowed numbers to be quickly multiplied to about three places of accuracy. Beginning in the early 20th century, mechanical [[calculator]]s, such as the [[Marchant Calculator|Marchant]], automated multiplication of up to 10-digit numbers. Modern electronic [[computer]]s and calculators have greatly reduced the need for multiplication by hand.

===Historical algorithms===
Methods of multiplication were documented in the writings of [[ancient Egypt]]ian, {{Citation needed span|text=Greek, Indian,|date=December 2021|reason=This claim is not sourced in the subsections below.}} and [[History of China#Ancient China|Chinese]] civilizations.

The [[Ishango bone]], dated to about 18,000 to 20,000&nbsp;BC, may hint at a knowledge of multiplication in the [[Upper Paleolithic]] era in [[Central Africa]], but this is speculative.<ref>{{cite arXiv|last=Pletser|first=Vladimir|date=2012-04-04|title=Does the Ishango Bone Indicate Knowledge of the Base 12? An Interpretation of a Prehistoric Discovery, the First Mathematical Tool of Humankind|class=math.HO|eprint=1204.1019}}</ref>{{Verification needed|date=December 2021}}

====Egyptians====
{{Main|Ancient Egyptian multiplication}}
The Egyptian method of multiplication of integers and fractions, which is documented in the [[Rhind Mathematical Papyrus]], was by successive additions and doubling. For instance, to find the product of 13 and 21 one had to double 21 three times, obtaining {{nowrap|1=2 × 21 = 42}}, {{nowrap|1=4 × 21 = 2 × 42 = 84}}, {{nowrap|1=8 × 21 =  2 × 84 = 168}}. The full product could then be found by adding the appropriate terms found in the doubling sequence:<ref>{{Cite web |title=Peasant Multiplication |url=http://www.cut-the-knot.org/Curriculum/Algebra/PeasantMultiplication.shtml |access-date=2021-12-29 |website=cut-the-knot.org}}</ref>
:13 × 21 = (1 + 4 + 8) × 21 = (1 × 21) + (4 × 21) + (8 × 21) = 21 + 84 + 168 = 273.

====Babylonians====
The [[Babylonians]] used a [[sexagesimal]] [[positional number system]], analogous to the modern-day [[decimal expansion|decimal system]]. Thus, Babylonian multiplication was very similar to modern decimal multiplication. Because of the relative difficulty of remembering {{nowrap|60 × 60}} different products, Babylonian mathematicians employed [[multiplication table]]s. These tables consisted of a list of the first twenty multiples of a certain ''principal number'' ''n'': ''n'', 2''n'', ..., 20''n''; followed by the multiples of 10''n'': 30''n'' 40''n'', and 50''n''. Then to compute any sexagesimal product, say 53''n'', one only needed to add 50''n'' and 3''n'' computed from the table.{{Citation needed|date=December 2021}}

====Chinese====
{{see also|Chinese multiplication table}}
[[File:Multiplication algorithm.GIF|thumb|right|upright 1.0|{{nowrap|1=38 × 76 = 2888}}]]
In the mathematical text ''[[Zhoubi Suanjing]]'', dated prior to 300&nbsp;BC, and the ''[[Nine Chapters on the Mathematical Art]]'', multiplication calculations were written out in words, although the early Chinese mathematicians employed [[Rod calculus]] involving place value addition, subtraction, multiplication, and division. The Chinese were already using a [[Chinese multiplication table|decimal multiplication table]] by the end of the [[Warring States]] period.<ref name="Nature">{{cite journal | url =http://www.nature.com/news/ancient-times-table-hidden-in-chinese-bamboo-strips-1.14482 | title =Ancient times table hidden in Chinese bamboo strips | journal =Nature | first =Jane |last=Qiu |author-link=Jane Qiu| date =7 January 2014 | access-date =22 January 2014 | doi =10.1038/nature.2014.14482 | s2cid =130132289 | archive-url =https://web.archive.org/web/20140122064930/http://www.nature.com/news/ancient-times-table-hidden-in-chinese-bamboo-strips-1.14482 | archive-date =22 January 2014 | url-status =live | doi-access =free }}</ref>

===Modern methods===
[[Image:Gelosia multiplication 45 256.png|right|upright 1.0|thumb|Product of 45 and 256. Note the order of the numerals in 45 is reversed down the left column. The carry step of the multiplication can be performed at the final stage of the calculation (in bold), returning the final product of {{nowrap|1=45 × 256 = 11520}}. This is a variant of [[Lattice multiplication]].]]
The modern method of multiplication based on the [[Hindu–Arabic numeral system]] was first described by [[Brahmagupta]]. Brahmagupta gave rules for addition, subtraction, multiplication, and division. [[Henry Burchard Fine]], then a professor of mathematics at [[Princeton University]], wrote the following:
:''The Indians are the inventors not only of the positional decimal system itself, but of most of the processes involved in elementary reckoning with the system. Addition and subtraction they performed quite as they are performed nowadays; multiplication they effected in many ways, ours among them, but division they did cumbrously.''<ref>{{cite book |last=Fine |first=Henry B. |author-link=Henry Burchard Fine |title=The Number System of Algebra – Treated Theoretically and Historically |edition=2nd |date=1907 |page=90 |url=https://archive.org/download/numbersystemofal00fineuoft/numbersystemofal00fineuoft.pdf}}</ref>
These place value decimal arithmetic algorithms were introduced to Arab countries by [[Al Khwarizmi]] in the early 9th&nbsp;century and popularized in the Western world by [[Fibonacci]] in the 13th century.<ref>{{Cite web |last=Bernhard |first=Adrienne |title=How modern mathematics emerged from a lost Islamic library |url=https://www.bbc.com/future/article/20201204-lost-islamic-library-maths |access-date=2022-04-22 |website=bbc.com |language=en}}</ref>

====Grid method====
[[Grid method multiplication]], or the box method, is used in primary schools in England and Wales and in some areas{{Which|date=December 2021}} of the United States to help teach an understanding of how multiple digit multiplication works. An example of multiplying 34 by 13 would be to lay the numbers out in a grid as follows:

:{| class="wikitable" style="text-align: center;"
! scope="col" | ×
! scope="col" | 30
! scope="col" | 4
|-
! scope="row" | 10
|300
|40
|-
! scope="row" | 3
|90
|12
|}

and then add the entries.

===Computer algorithms===
{{Main|Multiplication algorithm#Fast multiplication algorithms for large inputs}}
The classical method of multiplying two {{math|''n''}}-digit numbers requires {{math|''n''<sup>2</sup>}} digit multiplications. [[Multiplication algorithm]]s have been designed that reduce the computation time considerably when multiplying large numbers. Methods based on the [[Discrete Fourier transform#Multiplication of large integers|discrete Fourier transform]] reduce the [[computational complexity]] to {{math|''O''(''n'' log ''n'' log log ''n'')}}. In 2016, the factor {{math|log log ''n''}} was replaced by a function that increases much slower, though still not constant.<ref>{{Cite journal|last1=Harvey|first1=David|last2=van der Hoeven|first2=Joris|last3=Lecerf|first3=Grégoire|title=Even faster integer multiplication|date=2016|journal=Journal of Complexity|volume=36|pages=1–30|doi=10.1016/j.jco.2016.03.001|issn=0885-064X|arxiv=1407.3360|s2cid=205861906}}</ref> In March 2019, David Harvey and Joris van der Hoeven submitted a paper presenting an integer multiplication algorithm with a complexity of <math>O(n\log n).</math><ref>David Harvey, Joris Van Der Hoeven (2019). [https://hal.archives-ouvertes.fr/hal-02070778 Integer multiplication in time O(n log n)] {{Webarchive|url=https://web.archive.org/web/20190408180939/https://hal.archives-ouvertes.fr/hal-02070778 |date=2019-04-08 }}</ref> The algorithm, also based on the fast Fourier transform, is conjectured to be asymptotically optimal.<ref>{{Cite web|url=https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/|title=Mathematicians Discover the Perfect Way to Multiply|last=Hartnett|first=Kevin|website=Quanta Magazine|date=11 April 2019|language=en|access-date=2020-01-25}}</ref> The algorithm is not practically useful, as it only becomes faster for multiplying extremely large numbers (having more than {{math|2<sup>1729<sup>12</sup></sup>}} bits).<ref>{{Cite web|url=https://cacm.acm.org/magazines/2020/1/241707-multiplication-hits-the-speed-limit/fulltext|title=Multiplication Hits the Speed Limit|last=Klarreich|first=Erica|website=cacm.acm.org|date=January 2020 |language=en|access-date=2020-01-25|archive-url=https://archive.today/20201031123457/https://cacm.acm.org/magazines/2020/1/241707-multiplication-hits-the-speed-limit/fulltext|archive-date=2020-10-31|url-status=live}}</ref>