speed of mpq_cmp vs mpq_sub

Marc Glisse marc.glisse at inria.fr
Sun May 22 12:02:36 UTC 2016

On Sun, 22 May 2016, paul zimmermann wrote:

>       Marc,
> maybe mpq_cmp could first check if the denominators are equal, and in that
> case call mpz_cmp on the numerators, and in the other case do the expensive
> test I guess it is doing currently, i.e., a/b < c/d iff a*d < b*c. I guess
> some fast pre-test is done to check whether a*d and b*c could be in the same
> binade.
> Paul
> PS: note one could also check a=c first, but that should occur less frequently.

It isn't just the case where the 2 denominators are equal, a large gcd is 
sufficient. In the example I posted, if I multiply the denominator of y by 
3 and that of x by 5 (didn't check if that makes the mpq non canonical, 
but it shouldn't really matter), I still get sub in 1.8s and cmp in 25s. 
(if I multiply by 17 instead of 5, the magnitude tests kick in and make 
cmp a bit faster than sub)

So this seems to be a matter of what is most common when we compare x and 
y that are close enough that the magnitude is not sufficient to conclude. 
Do we often have denominators with a large gcd? A large power-of-2 factor? 
The same denominator? Nothing special?

Marc Glisse

More information about the gmp-discuss mailing list