Multiplication algorithm: Difference between revisions

Revision as of 11:38, 22 July 2023

Revision as of 15:43, 22 July 2023

Line 381:

{{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 |first2=V. |last2=Strassen |title=Schnelle Multiplikation großer Zahlen |journal=Computing |volume=7 |issue= 3–4|pages=281–292 |date=1971 |doi=10.1007/BF02242355 |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>

Every number in base B, can be written as a polynomial:

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

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

Furthermore, multiplication of two numbers could be thought of as a product of two polynomials:

Then we can say that,

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

Because,for <math> B^k </math>: <math>c_k =\sum_{(i,j):i+j=k}^k {a_ib_j} = \sum_{i=0}^k {a_ib_{k-i}} </math>,

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.

we have a convolution.

By using fft (fast fourier transformation), we can get

To remain in the modular setting of Fourier transforms, we look for a ring with a (2''m'')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\hat{f}(\sum_{i=0}^k {a_ib_{k-i}}) = 2\sum_{i=0}^k {3ma_ib_i} + 1.</math>. ¨

We have reduced our convolution problem

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

to product problem, through fft.

By finding ifft (polynomial interpolation), for each <math>c_k </math>, one get the desired coeffesients.

The algorithm has a time complexity of [[Bachmann-Landau notation|Θ]](''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.

Algorithm uses divide and conquer strategy, to divide problem to subproblems.

What is important, is to make subproblems of equal size. Using even and odd indexes, give subproblems of same size.

It han an time complexity of O(''n''&nbsp;log(''n'')&nbsp;log(log(''n''))).

==== History ====

TheAlgorithm basicwere ideainvented due toby [[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 |first2=V. |last2=Strassen |title=Schnelle Multiplikation großer Zahlen |journal=Computing |volume=7 |issue= 3–4|pages=281–292 |date=1971 |doi=10.1007/BF02242355 |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

=== Further improvements ===