Multiplication algorithm: Difference between revisions

Revision as of 21:15, 11 September 2014

Revision as of 16:02, 4 November 2014

Line 367:

=== Fourier transform methods ===

[[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">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 {a_i 2^{wi}a_i}\text{ and }b=\sum_{j=0}^m {b_j 2^{wj}b_j}.</math>

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

We can then say that

: <math>aba=\sum_{i=0}^m \sum_{j=0}^ma_i 2x^{w(i+j)}a_i b_j = \sum_{k=0}^{2m} 2^{wk} \sum_text{i=0}^k a_iand b_{k-i} b= \sum_{kj=0}^m {2m}b_j 2x^{wkj} c_k }.</math>

WeThen we can then say that,

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

by setting ''b''_''j'' = 0 and ''a''_''i'' = 0 for ''j'', ''i'' > ''m'', ''k'' = ''i'' + ''j'' and {''c''_''k''} as the [[convolution]] of {''a''_''i''} and {''b''_''j''}. Using the [[convolution theorem]] ''ab'' can be computed by

Line 383 ⟶ 387:

Another way to describe this process is forming polynomials whose coefficients are the digits of the inputs (in base 2^''w''), multiplying them rapidly using convolution by FFT, then extracting the coefficients of the result polynomial and performing carrying.

The [[Schönhage–Strassen algorithm]], described in 1971 by [[Arnold Schönhage|Schönhage]] and Strassen, 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]]) 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. However, these latter algorithms are only faster than Schönhage–Strassen for impractically large inputs.

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³².