Editing Multiplication algorithm (section)

===Schönhage–Strassen===
{{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<sup>''w''</sup> for illustrative purposes.]]

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

<math display="block"> X = \sum_{i=0}^N {x_iB^i} </math>

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

<math display="block">XY = (\sum_{i=0}^N {x_iB^i})(\sum_{j=0}^N {y_iB^j}) </math>

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

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

<math display="block"> \hat{f}(a * b) =  \hat{f}(\sum_{i=0}^k {a_ib_{k-i}}) =  \hat{f}(a) \bullet \hat{f}(b) </math>. That is; <math> C_k = a_k \bullet b_k </math>, where <math> C_k </math>
is the corresponding coefficient in fourier space. This can also be written as: <math>\mathrm{fft}(a * b) = \mathrm{fft}(a) \bullet \mathrm{fft}(b)</math>.


We have the same coefficient due to linearity under fourier transformation, and because these polynomials 
only consist of one unique term per coefficient:

<math display="block"> \hat{f}(x^n) = \left(\frac{i}{2\pi}\right)^n \delta^{(n)}  </math>  and 
<math display="block"> \hat{f}(a\, X(\xi) + b\, Y(\xi)) = a\, \hat{X}(\xi) + b\, \hat{Y}(\xi)</math>

* Convolution rule: <math> \hat{f}(X * Y) = \ \hat{f}(X)  \bullet \hat{f}(Y) </math>

We have reduced our convolution problem
to product problem, through fft.

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

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

It has a time complexity of O(''n''&nbsp;log(''n'')&nbsp;log(log(''n''))).

==== History ====

The algorithm was invented by [[Volker Strassen|Strassen]] (1968). It 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>