Multiplication algorithm: Difference between revisions

Revision as of 16:10, 22 July 2023

Revision as of 16:25, 22 July 2023

Line 396:

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

<math> \hat{f}(\sum_{i=0}^k {a_ib_{k-i}}) = \sum_{i=0}^k {A_iB_ia_ib_i} </math>. Where <math> A_i, B_i </math> are corresponding coeffecients in fourier space.

We have the same coeffesients due to linearity under fourier transformation, and because these polynomials

only consist of one unique term per coeffesient:<math> \hat{f}(x^n) = \left(\frac{i}{2\pi}\right)^n \delta^{(n)} </math> and

<math> \hat{f}(a\, X(\xi) + b\, Y(\xi)) = a\, \hat{X}(\xi) + b\, \hat{Y}(\xi)</math>

We have reduced our convolution problem