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