Multiplication's Complexity
Farnam Mansouri
mansouri.farnam at gmail.com
Mon Mar 3 20:11:12 UTC 2014
Hi,
I have a question regarding to the complexity of the FFT algorithm in
multiplication.
I couldn't quite understand the implemented algorithm and its complexity
based on the explanations on the page 96 of the manual (or
https://gmplib.org/manual/FFT-Multiplication.html#FFT-Multiplication). 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