# speed of mpq_cmp vs mpq_sub

Torbjörn Granlund tg at gmplib.org
Sun May 22 17:07:29 UTC 2016

```tg at gmplib.org (Torbjörn Granlund) writes:

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.

Optimising for a/b ~ c/d when high(b) = high(d).

Write b = shd * B^k + bl, and d = shd * B^k + dl.  Here, shd is "shared
high denominator", B is the limb base.

We then form the cross-products:

t1 = a * (shd * B^k + dl)
t2 = c * (shd * B^k + bl)

And compute their difference:

x = t1 - t2 =
= a * (shd * B^k + dl) - c * (shd * B^k + bl) =
= a * shd * B^k + a * dl - c * shd * B^k - c * bl =
= (a - c) * shd * B^k + a * dl - c * bl

If we have a large shd, this will save close to 1/2 of the work.  Not
too impressive in the light of the demonstrated performance issues.  But
if the numerators similarly have a common high part ("shn") then a - c
will largely cancel and now we should reach or beat mpq_sub's
performance for all operands.

--
Torbjörn