Content deleted Content added
merging "shift and add" into long division |
restructuring into "multiplication by hand algorithms" and "computational complexity" |
||
Line 2:
{{Use dmy dates|date=May 2019|cs1-dates=y}}
A '''multiplication algorithm''' is an [[algorithm]] (or method) to [[multiplication|multiply]] two numbers. Depending on the size of the numbers, different algorithms are used. Efficient multiplication algorithms have existed since the advent of the decimal system.
==Long multiplication==
Line 42 ⟶ 8:
multiply the [[wikt:multiplicand|multiplicand]] by each digit of the [[wikt:multiplier|multiplier]] and then add up all the properly shifted results. It requires memorization of the [[multiplication table]] for single digits.
This is the usual algorithm for multiplying larger numbers by hand in base 10
===Example===
Line 75 ⟶ 41:
When implemented in software, long multiplication algorithms must deal with overflow during additions, which can be expensive. A typical solution is to represent the number in a small base, ''b'', such that, for example, 8''b'' is a representable machine integer. Several additions can then be performed before an overflow occurs. When the number becomes too large, we add part of it to the result, or we carry and map the remaining part back to a number that is less than ''b''. This process is called ''normalization''. Richard Brent used this approach in his Fortran package, MP.<ref>{{cite journal|first1=Richard P|last1=Brent|title=A Fortran Multiple-Precision Arithmetic Package. |doi=10.1145/355769.355775|journal=ACM Transactions on Mathematical Software|date=March 1978|volume=4|pages=57–70|citeseerx=10.1.1.117.8425|s2cid=8875817}}</ref>
Computers initially used a very similar algorithm to long multiplication in base 2, but modern processors have optimized circuitry for fast multiplications using more efficient algorithms, at the price of a more complex hardware realization.{{cn}} In base two, long multiplication is sometimes called '''"shift and add"''', because the algorithm simplifies and just consists of shifting left (multiplying by powers of two) and adding. Most currently available microprocessors implement this or other similar algorithms (such as [[Booth encoding]]) for various integer and floating-point sizes in [[hardware multiplier]]s or in [[microcode]].{{cn}}
On currently available processors, a bit-wise shift instruction is faster than a multiply instruction and can be used to multiply (shift left) and divide (shift right) by powers of two. Multiplication by a constant and [[division algorithm#Division by a constant|division by a constant]] can be implemented using a sequence of shifts and adds or subtracts. For example, there are several ways to multiply by 10 using only bit-shift and addition.
Line 84 ⟶ 50:
In some cases such sequences of shifts and adds or subtracts will outperform hardware multipliers and especially dividers. A division by a number of the form <math>2^n</math> or <math>2^n \pm 1</math> often can be converted to such a short sequence.
==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>Gary Eason, [http://news.bbc.co.uk/1/hi/education/639937.stm Back to school for parents], ''[[BBC News]]'', 13 February 2000<br>[[Rob Eastaway]], [https://www.bbc.co.uk/news/magazine-11258175 Why parents can't do maths today], ''[[BBC News]]'', 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.]]
Line 97 ⟶ 101:
* 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.
{|
Line 143 ⟶ 147:
|}
===Russian
{{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 |author=D. Wells | author-link=David G. Wells | year=1987 |page=44 |title=The Penguin Dictionary of Curious and Interesting Numbers |publisher=Penguin Books}}</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====
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.
Line 199 ⟶ 203:
139676498390 10000010000101010111100011100111010110
===Quarter square multiplication===
Two quantities can be multiplied using quarter squares by employing the following identity involving the [[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 |isbn= 978-0691091822 }}</ref> attribute to [[Babylonian mathematics]] (2000–1600 BC).
Line 225 ⟶ 229:
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>-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>-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
==Computational complexity of multiplication==
{{unsolved|computer science|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}
{{merge from|Fürer's algorithm|discuss=Talk:Multiplication algorithm#Merger proposal|date=February 2022}}
===Karatsuba multiplication===
Line 322 ⟶ 294:
Using [[number-theoretic transform]]s instead of [[discrete Fourier transform]]s avoids [[rounding error]] problems by using modular arithmetic instead of [[floating point|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''<sup>2</sup>), where ''k'' is a [[Mersenne prime]], allows the use of a transform sized to a power of 2; e.g. {{nowrap|1=''k'' = 2<sup>31</sup> − 1}} supports transform sizes up to 2<sup>32</sup>.
===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<sup>0</sup>[''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<sub>''p''</sub> gates that can compute a product. This follows from a constant-depth reduction of MOD<sub>''q''</sub> to multiplication.<ref>Sanjeev Arora and Boaz Barak, ''Computational Complexity: A Modern Approach'', Cambridge University Press, 2009.</ref> Lower bounds for multiplication are also known for some classes of [[branching program]]s.<ref>Farid Ablayev and Marek Karpinski, ''A lower bound for integer multiplication on randomized ordered read-once branching programs'', Information and Computation 186 (2003), 78–89.</ref>
==Complex number multiplication==
Complex multiplication normally involves four multiplications and two additions.
:<math>(a+bi) (c+di) = (ac-bd) + (bc+ad)i.</math>
Or
:<math>
\begin{array}{c|c|c}
\times & a & bi \\
\hline
c & ac & bci \\
\hline
di & adi & -bd
\end{array}
</math>
But there is a way of reducing the number of multiplications to three.<ref name="taocp-vol2-sec464-ex41">{{Citation | last1=Knuth | first1=Donald E. | author1-link=Donald Knuth | title=The Art of Computer Programming volume 2: Seminumerical algorithms | publisher=[[Addison-Wesley]] | year=1988 | pages=519, 706| title-link=The Art of Computer Programming }}
</ref>
The product (''a'' + ''bi'') · (''c'' + ''di'') can be calculated in the following way.
:''k''<sub>1</sub> = ''c'' · (''a'' + ''b'')
:''k''<sub>2</sub> = ''a'' · (''d'' − ''c'')
:''k''<sub>3</sub> = ''b'' · (''c'' + ''d'')
:Real part = ''k''<sub>1</sub> − ''k''<sub>3</sub>
:Imaginary part = ''k''<sub>1</sub> + ''k''<sub>2</sub>.
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'' + ''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>P. Duhamel and M. Vetterli, [http://math.berkeley.edu/~strain/273.F10/duhamel.vetterli.fft.review.pdf Fast Fourier transforms: A tutorial review and a state of the art"] {{webarchive|url=https://web.archive.org/web/20140529212847/http://math.berkeley.edu/~strain/273.F10/duhamel.vetterli.fft.review.pdf |date=2014-05-29 }}, ''Signal Processing'' vol. 19, pp. 259–299 (1990), section 4.1.</ref> However, trading off a multiplication for an addition in this way may no longer be beneficial with modern [[floating-point unit]]s.<ref>S. G. Johnson and M. Frigo, "[http://fftw.org/newsplit.pdf A modified split-radix FFT with fewer arithmetic operations]," ''IEEE Trans. Signal Process.'' vol. 55, pp. 111–119 (2007), section IV.</ref>
==Polynomial multiplication==
| |||