Multiplication algorithm: Difference between revisions

Revision as of 01:42, 10 August 2015

Revision as of 14:20, 13 August 2015

Line 1:

A '''multiplication algorithm''' is an [[algorithm]] (or method) to [[multiplication|multiply]] two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.

== 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]] level. 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]], [http://www.bbc.co.uk/news/magazine-11258175 Why parents can't do maths today], ''[[BBC News]]'', 10 September 2010</ref>

Line 7:

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 &times;× 13, for example, could be computed using the grid:

<div style="float:right">

<pre> 300

Line 35:

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.

== Long multiplication ==

If a [[numeral system|positional numeral system]] is used, a natural way of multiplying numbers is taught in schools

as '''long multiplication''', sometimes called '''grade-school multiplication''', sometimes called '''Standard Algorithm''':

Line 70:

</source>

=== Space complexity ===

{{unreferenced section|date=September 2012}}

Let ''n'' be the total number of digits in the two input numbers in [[Radix|base]] ''D''. If the result must be kept in memory then the space complexity is trivially Θ(''n''). However in certain applications, the entire result need not be kept in memory and instead digits of results can be streamed out as they are computed (for example, to system console or file). In these scenarios, long multiplication has the advantage that it can easily be formulated as a [[FL (complexity)|log space]] algorithm; that is, an algorithm that only needs working space proportional to the logarithm of the number of digits in the input (Θ(log&nbsp;''n'')). This is the ''double'' logarithm of the numbers being multiplied themselves (log&nbsp;log&nbsp;''N''). Note that operands themselves still need to be kept in memory and their Θ(''n'') space is not considered in this analysis.

Line 89:

'''for''' bi = MAX(1, ri - p + 1) to MIN(ri, q) //Digits from b that need to be considered

ai ← ri − bi + 1 //Digits from a follow "symmetry"

sum ← sum + (a[ai] &times;× b[bi])

result[ri] ← sum mod base

sum ← floor(sum / base)

result[p+q] ← sum mod base //Last digit of the result comes from last carry

=== Electronic usage ===

Some [[Integrated circuit|chips]] implement this algorithm for various integer and floating-point sizes in [[computer hardware]] or in [[microcode]]. In [[arbitrary-precision arithmetic]], it's common to use long multiplication with the base set to 2^''w'', where ''w'' is the number of bits in a word, for multiplying relatively small numbers.

Line 101:

When implemented in software, long multiplication algorithms have to deal with overflow during additions, which can be expensive. For this reason, a typical approach is to represent the number in a small base ''b'' such that, for example, 8''b''² is a representable machine integer (for example Richard Brent used this approach in his Fortran package MP<ref>Richard P. Brent. A Fortran Multiple-Precision Arithmetic Package. Australian National University. March 1978.</ref>); we can then perform several additions before having to deal with overflow. When the number becomes too large, we add part of it to the result or carry and map the remaining part back to a number less than ''b''; this process is called ''normalization''.

== 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 161:

|}

== Peasant or binary multiplication ==

{{Main|Peasant multiplication}}

{{unreferenced section|date=January 2013}}

Line 221:

139676498390 10000010000101010111100011100111010110

== Shift and add ==

Historically, computers used a "shift and add" algorithm to multiply small integers. Both base 2 [[#Long multiplication|long multiplication]] and base 2 [[peasant multiplication]] reduce to this same algorithm.

In base 2, multiplying by the single digit of the multiplier reduces to a simple series of [[logical AND]] operations. Each partial product is added to a running sum as soon as each partial product is computed. 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]].

Line 251:

|{{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|&lfloor;⌊''n''²/4&rfloor;4⌋}} || 0 || 0 || 1 || 2 || 4 || 6 || 9 || 12 || 16 || 20 || 25 || 30 || 36 || 42 || 49 || 56 || 64 || 72 || 81

|}

Line 325:

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.

== Fast multiplication algorithms for large inputs ==

{{unsolved|computer science|What is the fastest algorithm for multiplication of two n-digit numbers?}}

Line 345:

</math>

By 1805 [[Gauss]] had discovered a way of reducing the number of multiplications to three.<ref>{{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}}

</ref>

Line 351:

:''k''₁ = ''c'' · (''a'' + ''b'')

:''k''₂ = ''a'' · (''d'' &minus;− ''c'')

:''k''₃ = ''b'' · (''c'' + ''d'')

:Real part = ''k''₁ &minus;− ''k''₃

:Imaginary part = ''k''₁ + ''k''₂.

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''&minus;−''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"], ''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 Processing'' vol. 55, pp. 111–119 (2007), section IV.</ref>

===Karatsuba multiplication===

Line 382:

Although using more and more parts can reduce the time spent on recursive multiplications further, the overhead from additions and digit management also grows. For this reason, the method of Fourier transforms is typically faster for numbers with several thousand digits, and asymptotically faster for even larger numbers.

=== Fourier transform methods ===

[[File:Integer multiplication by FFT.svg|thumb|350px|Demonstration of multiplying 1234 &times;× 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">A. Schönhage and V. Strassen, "Schnelle Multiplikation großer Zahlen", ''Computing'' '''7''' (1971), pp. 281–292.</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>

We look at these numbers as polynomials in ''x'', where ''x = 2^w'', to get,

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

Then we can then say that,

: <math>ab=\sum_{i=0}^{m-1} \sum_{j=0}^{m-1} a_i b_j x^{(i+j)} = \sum_{k=0}^{2m-2} c_k x^{k} </math>

Line 398:

Clearly the above setting is realized by polynomial multiplication, of two polynomials ''a'' and ''b''. The crucial step now, is to use [[Discrete_Fourier_transform#Polynomial_multiplication|Fast Fourier multiplication]] of polynomials, to realize the multiplications above faster than in naive ''O(m²)'' time.

To remain in the modular setting of Fourier transforms, we look for a ring with a ''2m^th'' root of unity. hence we do multiplication modulo ''N'' (and thus in the ''Z/NZ'' [[Ring (mathematics)|ring]]). Further, N must be chosen so that there is no 'wrap around', essentially, no reductions modulo N occur. Thus, the choice of N is crucial. For example, it could be done as,

: <math> N = 2^{3w} + 1 </math>

The ring ''Z/NZ'' would thus have a ''2m^th'' root of unity, namely 8. Also, it can be checked that ''c_k < N'', and thus no wrap around will occur.

The algorithm has a time complexity of Θ(''n''&nbsp;log(''n'')&nbsp;log(log(''n''))) and is used in practice for numbers with more than 10,000 to 40,000 decimal digits. In 2007 this was improved by Martin Fürer ([[Fürer's algorithm]]) <ref name="fürer_1">Fürer, M. (2007). "[http://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf Faster Integer Multiplication]" in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11–13, 2007, San Diego, California, USA</ref> to give a time complexity of ''n''&nbsp;log(''n'')&nbsp;2^{Θ(log^*(''n''))} using Fourier transforms over complex numbers. Anindya De, Chandan Saha, Piyush Kurur and Ramprasad Saptharishi<ref>Anindya De, Piyush P Kurur, Chandan Saha, Ramprasad Saptharishi. Fast Integer Multiplication Using Modular Arithmetic. Symposium on Theory of Computation (STOC) 2008.</ref> gave a similar algorithm using [[modular arithmetic]] in 2008 achieving the same running time. In context of the above material, what these latter authors have achieved is to find ''N'' much less than ''2^3k + 1'', so that ''Z/NZ'' has a ''2m^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.

Line 408:

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 ''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. ''k'' = 2³¹-1 supports transform sizes up to 2³².

== Lower bounds ==

There is a trivial lower bound of Ω(''n'') for multiplying two ''n''-bit numbers on a single processor; no matching algorithm (on conventional Turing machines) nor any better 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>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>

== Polynomial multiplication ==

{{Expand section|date=October 2008}}

All the above multiplication algorithms can also be expanded to multiply [[polynomial]]s. For instance the Strassen algorithm may be used for polynomial multiplication<ref>{{cite web|url=http://everything2.com/title/Strassen+algorithm+for+polynomial+multiplication|title=Strassen algorithm for polynomial multiplication |publisher=Everything2}}</ref>

Line 434:

* [[Horner scheme]] for evaluation of a polynomial

== References ==

{{Reflist}}

<references />

==External links==