Multiplication algorithm: Difference between revisions

Revision as of 20:23, 9 November 2022

Revision as of 11:13, 6 December 2022

Line 71:

===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.

Line 108:

[[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. (2010). |title=The Ottoman Palace School Enderun and Thethe 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), pp. |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}}

Line 164:

===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 |authorfirst=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><ref>{{Citation|title=Cool Multiplication Math Trick|url=https://www.youtube.com/watch?v=dtfz5U8bt8A |archive-url=https://ghostarchive.org/varchive/youtube/20211211/dtfz5U8bt8A| archive-date=2021-12-11 |url-status=live|language=en|access-date=2020-03-14}}{{cbignore}}</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====

Line 244:

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⁹&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⁹&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 also benefitted 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>{{CitationCite journal |last = Putney |first = Charles |title = Fastest 6502 Multiplication Yet|date = MarMarch 1986 |periodicaljournal = Apple Assembly Line |volume = 6 |issue = 6 |url = http://www.txbobsc.com/aal/1986/aal8603.html#a5}}</ref>

==Computational complexity of multiplication==

Line 252:

A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).

The algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal | last1 = Harvey | first1 = David | last2 = van der Hoeven | first2 = Joris | author2-link = Joris van der Hoeven | doi = 10.4007/annals.2021.193.2.4 | issue = 2 | journal = [[Annals of Mathematics]] | mr = 4224716 | pages = 563–617 | series = Second Series | title = Integer multiplication in time <math>O(n \log n)</math> | volume = 193 | year = 2021| s2cid = 109934776 | url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.

===Karatsuba multiplication===

Line 279:

{{Main|Schönhage–Strassen algorithm}}

[[File:Integer multiplication by FFT.svg|thumb|350px|Demonstration of multiplying 1234 × 5678 = 7006652 using fast Fourier transforms (FFTs). [[Number-theoretic transform]]s in the integers modulo 337 are used, selecting 85 as an 8th root of unity. Base 10 is used in place of base 2^''w'' for illustrative purposes.]]

The basic idea due to [[Volker Strassen|Strassen]] (1968) is to use fast polynomial multiplication to perform fast integer multiplication. The algorithm was made practical and theoretical guarantees were provided in 1971 by [[Arnold Schönhage|Schönhage]] and Strassen resulting in the [[Schönhage–Strassen algorithm]].<ref name="schönhage">{{cite journal |first1=A. |last1=Schönhage and |first2=V. |last2=Strassen, "|title=Schnelle Multiplikation großer Zahlen", ''|journal=Computing'' '''|volume=7''' (|issue= 3–4|pages=281–292 |date=1971), pp|doi=10.1007/BF02242355 281–292|s2cid=9738629 |url=https://link.springer.com/article/10.1007/BF02242355}}</ref> The details are the following: We choose the largest integer ''w'' that will not cause [[Integer overflow|overflow]] during the process outlined below. Then we split the two numbers into ''m'' groups of ''w'' bits as follows

: <math>a=\sum_{i=0}^{m-1} {a_i 2^{wi}}\text{ and }b=\sum_{j=0}^{m-1} {b_j 2^{wj}}.</math>

Line 303:

=== Further improvements ===

In 2007 the [[asymptotic complexity]] of integer multiplication was improved by the Swiss mathematician [[Martin Fürer]] of Pennsylvania State University to ''n''&nbsp;log(''n'')&nbsp;2^{Θ([[iterated logarithm|log^*]](''n''))} using Fourier transforms over complex numbers.<ref name="fürer_1">Fürer,{{cite book |first=M. (2007).|last=Fürer "[|chapter=Faster Integer Multiplication |chapter-url=https://webivv5hpp.archiveuni-muenster.orgde/webu/20130425232048/http:cl/WS2007-8/wwwmult.cse.psupdf |doi=10.edu1145/~furer/Papers/mult1250790.pdf Faster Integer Multiplication]" in1250800 |title=Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11–13, 2007, San Diego, California, USA |publisher= |___location= |date=2007 |isbn=978-1-59593-631-8 |pages=57–66 |s2cid=8437794 |url=}}</ref> Anindya De, Chandan Saha, Piyush Kurur and Ramprasad Saptharishi gave a similar algorithm using [[modular arithmetic]] in 2008 achieving the same running time.<ref>{{cite book |first1=A. |last1=De, |first2=C. |last2=Saha, |first3=P. |last3=Kurur and |first4=R. |last4=Saptharishi (2008). "|chapter=Fast integer multiplication using modular arithmetic" ''|chapter-url= |doi=10.1145/1374376.1374447 |title=Proceedings of the 40th annual ACM Symposium on Theory of Computing'' (STOC), 499–506,|publisher= New York, NY,|___location= |date=2008, and|isbn=978-1-60558-047-0 ''SIAM|pages=499–506 Journal|url= on Computing'', Vol. 42 Issue 2, 685–699, 2013. {{arXiv|arxiv=0801.1416|s2cid=3264828 }}</ref> In context of the above material, what these latter authors have achieved is to find ''N'' much less than 2^3''k'' + 1, so that ''Z''/''NZ'' has a (2''m'')th root of unity. This speeds up computation and reduces the time complexity. However, these latter algorithms are only faster than Schönhage–Strassen for impractically large inputs.

In 2015, Harvey, [[Joris van der Hoeven]] and Lecerf<ref>{{cite arXiv |first1=D. |last1=Harvey, |first2=J. |last2=van der Hoeven and |first3=G. |last3=Lecerf (|year=2015). "|title=Even faster integer multiplication", February 2015|class=cs.CC {{arXiv|eprint=1407.3360}}</ref> gave a new algorithm that achieves a running time of <math>O(n\log n \cdot 2^{3\log^* n})</math>, making explicit the implied constant in the <math>O(\log^* n)</math> exponent. They also proposed a variant of their algorithm which achieves <math>O(n\log n \cdot 2^{2\log^* n})</math> but whose validity relies on standard conjectures about the distribution of [[Mersenne prime]]s. In 2016, Covanov and Thomé proposed an integer multiplication algorithm based on a generalization of [[Fermat primes]] that conjecturally achieves a complexity bound of <math>O(n\log n \cdot 2^{2\log^* n})</math>. This matches the 2015 conditional result of Harvey, van der Hoeven, and Lecerf but uses a different algorithm and relies on a different conjecture.<ref>{{cite journal |first1=Svyatoslav |last1=Covanov |first2=Emmanuel |last2=Thomé |title=Fast Integer Multiplication Using Generalized Fermat Primes |journal=[[Mathematics of Computation|Math. Comp.]] |volume=88 |year=2019 |issue=317 |pages=1449–1477 |doi=10.1090/mcom/3367 |arxiv=1502.02800 |s2cid=67790860 }}</ref> In 2018, Harvey and van der Hoeven used an approach based on the existence of short lattice vectors guaranteed by [[Minkowski's theorem]] to prove an unconditional complexity bound of <math>O(n\log n \cdot 2^{2\log^* n})</math>.<ref>{{cite journal |first1=D. |last1=Harvey and |first2=J. |last2=van der Hoeven (2018).|year=2019 "|title=Faster integer multiplication using short lattice vectors", February|journal=The 2018Open Book Series |volume=2 |pages=293–310 |doi=10.2140/obs.2019.2.293 {{arXiv|arxiv=1802.07932|s2cid=3464567 }}</ref>

In March 2019, [[David Harvey (mathematician)|David Harvey]] and [[Joris van der Hoeven]] announced their discovery of an {{nowrap|''O''(''n'' log ''n'')}} multiplication algorithm.<ref>{{Cite magazine|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|magazine=Quanta Magazine|date=11 April 2019|access-date=2019-05-03}}</ref> It was published in the ''[[Annals of Mathematics]]'' in 2021.<ref>{{cite journal | last1 = Harvey | first1 = David | last2 = van der Hoeven | first2 = Joris | author2-link = Joris van der Hoeven | doi = 10.4007/annals.2021.193.2.4 | issue = 2 | journal = [[Annals of Mathematics]] | mr = 4224716 | pages = 563–617 | series = Second Series | title = Integer multiplication in time <math>O(n \log n)</math> | volume = 193 | year = 2021| s2cid = 109934776 | url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> Because Schönhage and Strassen predicted that ''n''&nbsp;log(''n'') is the ‘best possible’ result Harvey said: “...our work is expected to be the end of the road for this problem, although we don't know yet how to prove this rigorously.”<ref>{{cite news |last1=Gilbert |first1=Lachlan |title=Maths whiz solves 48-year-old multiplication problem |url=https://newsroom.unsw.edu.au/news/science-tech/maths-whiz-solves-48-year-old-multiplication-problem |access-date=18 April 2019 |publisher=UNSW |date=4 April 2019}}</ref>

Using [[number-theoretic transform]]s instead of [[discrete Fourier transform]]s avoids [[rounding error]] problems by using modular arithmetic instead of [[floating-point arithmetic]]. In order to apply the factoring which enables the FFT to work, the length of the transform must be factorable to small primes and must be a factor of {{nowrap|''N'' − 1}}, where ''N'' is the field size. In particular, calculation using a Galois field GF(''k''²), where ''k'' is a [[Mersenne prime]], allows the use of a transform sized to a power of 2; e.g. {{nowrap|1=''k'' = 2³¹ − 1}} supports transform sizes up to 2³².

===Lower bounds===

There is a trivial lower bound of [[Big O notation#Family of Bachmann–Landau notations|Ω]](''n'') for multiplying two ''n''-bit numbers on a single processor; no matching algorithm (on conventional machines, that is on Turing equivalent machines) nor any sharper lower bound is known. Multiplication lies outside of [[ACC0|AC⁰[''p'']]] for any prime ''p'', meaning there is no family of constant-depth, polynomial (or even subexponential) size circuits using AND, OR, NOT, and MOD_''p'' gates that can compute a product. This follows from a constant-depth reduction of MOD_''q'' to multiplication.<ref>{{cite book |first1=Sanjeev |last1=Arora and |first2=Boaz |last2=Barak, ''|title=Computational Complexity: A Modern Approach'', |publisher=Cambridge University Press, |date=2009. |isbn=978-0-521-42426-4 |url={{GBurl|8Wjqvsoo48MC|pg=PR7}}}}</ref> Lower bounds for multiplication are also known for some classes of [[branching program]]s.<ref>Farid{{cite Ablayevjournal and|first1=F. Marek|last1=Ablayev |first2=M. |last2=Karpinski, ''|title=A lower bound for integer multiplication on randomized ordered read-once branching programs'', |journal=Information and Computation |volume=186 (|issue=1 |pages=78–89 |date=2003 |doi=10.1016/S0890-5401(03),00118-4 78–89|url=https://core.ac.uk/download/pdf/82445954.pdf}}</ref>

==Complex number multiplication==

Line 342:

This algorithm uses only three multiplications, rather than four, and five additions or subtractions rather than two. If a multiply is more expensive than three adds or subtracts, as when calculating by hand, then there is a gain in speed. On modern computers a multiply and an add can take about the same time so there may be no speed gain. There is a trade-off in that there may be some loss of precision when using floating point.

For [[fast Fourier transform]]s (FFTs) (or any [[Linear map|linear transformation]]) the complex multiplies are by constant coefficients ''c''&nbsp;+&nbsp;''di'' (called [[twiddle factor]]s in FFTs), in which case two of the additions (''d''−''c'' and ''c''+''d'') can be precomputed. Hence, only three multiplies and three adds are required.<ref>{{cite journal |first1=P. |last1=Duhamel and |first2=M. |last2=Vetterli, [http://math.berkeley.edu/~strain/273.F10/duhamel.vetterli.fft.review.pdf |title=Fast Fourier transforms: A tutorial review and a state of the art"] {{webarchive|urljournal=https://web.archive.org/web/20140529212847/http://math.berkeley.edu/~strain/273.F10/duhamel.vetterli.fft.review.pdfSignal Processing |datevolume=2014-05-2919 }},|issue=4 ''Signal|pages=259–299 Processing''See vol.Section 19, pp4.1 259–299|date=1990 |doi=10.1016/0165-1684(199090),90158-U section 4|url=https://core.1ac.uk/download/pdf/147907050.pdf}}</ref> However, trading off a multiplication for an addition in this way may no longer be beneficial with modern [[floating-point unit]]s.<ref>{{cite journal |first1=S. G. |last1=Johnson and |first2=M. |last2=Frigo, "[http://fftw.org/newsplit.pdf |title=A modified split-radix FFT with fewer arithmetic operations]," ''|journal=IEEE Trans. Signal Process.'' vol. |volume=55, pp.|issue= 111–1191|pages=111–9 (2007),See sectionSection IV |date=2007 |doi=10.1109/TSP.2006.882087 |bibcode=2007ITSP...55..111J |s2cid=14772428 |url=https://www.fftw.org/newsplit.pdf }}</ref>

==Polynomial multiplication==