speed of mpq_cmp vs mpq_sub
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.
More information about the gmp-discuss