speed of mpq_cmp vs mpq_sub

Torbjörn Granlund tg at gmplib.org
Sun May 22 15:44:26 UTC 2016

Marc Glisse <marc.glisse at inria.fr> writes:

  Yes, the exact constant doesn't change much. Essentially, mpq_sub is
  done in linear time: gcd can be computed with just a few subtractions,
  divexact can be done in constant time since the output has constant
  size, and all we have left are some linear-time mul_1 and sub. And cmp
  takes whatever time mul takes. I just hope this case is rare enough.

Yep, the gcd call becomes very fast, I just noticed that.

I suppose we could do something fancy in cmp with stripping high parts
of the numerators and denominators when they match (highpart(num1) =
highpart(num2), and highpart(den1) = highpart(den2)) before we

Please encrypt, key id 0xC8601622

More information about the gmp-discuss mailing list