Multiplication's Complexity

Torbjorn Granlund tg at
Mon Mar 3 20:55:41 UTC 2014

Farnam Mansouri <mansouri.farnam at> writes:

  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)?
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

Please encrypt, key id 0xC8601622

More information about the gmp-discuss mailing list