speed of mpq_cmp vs mpq_sub

Marc Glisse marc.glisse at inria.fr
Sun May 22 14:33:00 UTC 2016

On Sun, 22 May 2016, Torbjörn Granlund wrote:

> Marc Glisse <marc.glisse at inria.fr> writes:
>  I am also surprised, but it is rather easy to reproduce. Maybe you'll
>  see a bug in my test program?
> Your program looks OK.
> I suppose multiplying 3 and 5 might make mpq_sub measurements unreliable
> if the result of the multiplying yielded non-canonical form.
> Using some other constants which are less likely to be contained in the
> operands might be a lazy fix (say 101 and 103).

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.

Marc Glisse

More information about the gmp-discuss mailing list