speed of mpq_cmp vs mpq_sub
marc.glisse at inria.fr
Sun May 22 18:01:45 UTC 2016
On Sun, 22 May 2016, Torbjörn Granlund wrote:
> 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
Note that after the multiplications by 3 and 5 (or 101 and 103), the
highparts are different. Or even simpler if den2 = 2 * den1. So this would
only apply in a few cases.
More information about the gmp-discuss