Multiplication's Complexity

[Torbjorn Granlund]

Farnam Mansouri <mansouri.farnam at gmail.com> writes:

  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)?
  
You are misreading the manual.  The GMP multiply code runs at O(n log n
log log n) time for multiplying two number which produce a n-bit
product.

Torbjörn
Please encrypt, key id 0xC8601622