mpq_cmp

Torbjörn Granlund tg at gmplib.org
Fri May 27 14:47:17 UTC 2016


[Trimming gmp-discuss, this is getting out-of-scope for that list.
I will mail a note to that list and ask for follow-up here.]

  Do I understand things correctly, so far?
  
My understanding agree 100% with yours, thus far.  :-)

  Let's make things a little more abstract, and observe that what we're
  computing is the sign of the determinant of the matrix (a, b ; c, d).

I need a bit more time to digest the rest of your reasoning.

I think I slightly disagree with your test order.  Bit count comparison
(i.e., (log(a)-log(b)) - (log(c)-log(d))) is O(1) and should go first,
directly after O(1) sign checks.

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.)

-- 
Torbjörn
Please encrypt, key id 0xC8601622


More information about the gmp-devel mailing list