Multiplication algorithm: Difference between revisions

Revision as of 16:35, 22 July 2023

Revision as of 17:00, 22 July 2023

Line 396:

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

<math> \hat{f}(\sum_{i=0}^k {a_ib_{k-i}}) = \sum_{i=0}^k {a_ib_i}a_i</math> ● <math> b_i </math>

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