mpq_cmp

[Niels Möller]

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

> Equality comparison might be O(1) for random input, but since the worst
> case is O(n) we should probably put it after bit counting.  (Of course,
> the "worst case" is in a sense the best case, as we can then exit at
> total cost O(n); but of course other O(n) cases will exist which do not
> allow early exits.)

Doing the comparisons early makes more sense if we have some clever
trick to take advantage of cancellation in the case that many but not
all limbs are equal.

E.g, if we compare 1112/17 to 1111/15, we want the (sign of the)
determinant of

  1112 17
  1111 15

Subtracting the second row from the first gives a new matrix

     1  2
  1111 15

with cheaper cross multiplies, thanks to cancellation, and the same
determinant. We could go one step further and subtract twice the first
column from the second (still leaving the determinant unchanged),
getting

     1      0
  1111  -2207

and the determinant is 1 * (-2207) - 1111 * 0. We find it negative by
examining signs only, and can conclude that 1112/17 < 1111/15, almost
without any multiplies at all. In this case, another alternative for the
second would be to subtract the first column from the second (no
doubling), that would give

     1      1
  1111  -1096

and now sgn (det (...) = sgn(-1096 - 1111), without any multiply at
all.

And in this examples, there are no non-trivial gcds, involved, right?
(And in fact, 2207, the absolute value of the determinant, happens to be
a prime).

For reference, the main rule about determinants is that adding any
multiple of one row to a different row, or adding a multiple of any
column to a different column, leaves the determinant invariant. Also,
multiplying a single row or column by a scalar multiplies the
determinant by the same scalar, which is why we can take out the gcd of
any row or column without changing the sign.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.