speed of mpq_cmp vs mpq_sub

Marc Glisse 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
> cross-multiply.

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.

-- 
Marc Glisse


More information about the gmp-discuss mailing list