Multiplication algorithm: Difference between revisions

Revision as of 16:31, 22 July 2023

Revision as of 16:32, 22 July 2023

Line 394:

we have a convolution.

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} </math>

Line 403:

Convolution rule, that is used, says: <math> \hat{f}(X * Y) = \ \hat{f}(X) </math> ● <math> \hat{f}(Y) </math>