Multiplication algorithm: Difference between revisions

Revision as of 15:45, 22 July 2023

Revision as of 16:02, 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.

In general, if one have two function f and g; then:

<math> \hat{f}(X * Y) = \hat{X}</math> • <math>\hat{Y} </math>

We have reduced our convolution problem