[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 _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel