speed of mpq_cmp vs mpq_sub

[Torbjörn Granlund]

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
Please encrypt, key id 0xC8601622