Multiplication's Complexity

Farnam Mansouri mansouri.farnam at
Mon Mar 3 20:11:12 UTC 2014


I have a question regarding to the complexity of the FFT algorithm in

I couldn't quite understand the implemented algorithm and its complexity
based on the explanations on the page 96 of the manual (or It
is mentioned that the Schonhage-&-Strassen algorithm is being used; but the
complexity of the algorithm is O(N^(k/(k-1))), whereas in other
literatures, it can be found that the complexity of the
Schonhage-&-Strassen algorithm is in the order of O(N log N log log N). I
know that there are multiple level of recursion for integer multiplication
(for point-wise multiplication) but how can the complexity of the algorithm
be like that (without any factor of "log" which I beleive every FFT-based
algorithm should have it somehow)?

Can someone please explain that to me.

P.S. I am using GMP integer multiplication (for extremely large integers)
in some of my algorithms. As a result the complexity of my algorithm
depends on the complexity of GMP's FFT multiplication.

Thanks in advanced,

More information about the gmp-discuss mailing list