Multiplication algorithm: Difference between revisions

Revision as of 20:39, 22 July 2023

Revision as of 14:06, 23 July 2023

Line 397:

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

is the corresponding coeffesient in fourier space. This can also be written as: fft(a * b) = fft(a) ● fft(b).

Line 416:

Algorithm uses divide and conquer strategy, to divide problem to subproblems.

What is important, is to make subproblems of equal size. Using even and odd indexes, give subproblems of same size.

It has a time complexity of O(''n''&nbsp;log(''n'')&nbsp;log(log(''n''))).