Multiplication algorithm: Difference between revisions

Revision as of 17:07, 22 July 2023

Revision as of 17:09, 22 July 2023

Line 396:

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

<math> \hat{f}(a * b) = \hat{f}(\sum_{i=0}^k {a_ib_{k-i}}) = a</math> ● <math> b </math>. That is; <math> \hat{f}(c_k)C_k = a_k </math> ● <math> b_k </math>, where <math> C_k </math>

is the corresponding coeffesient in fourier space.