speed of mpq_cmp vs mpq_sub
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