Torbjörn Granlund tg at
Sun May 29 14:22:22 UTC 2016

I completely agree with your reasoning about determinants.

And yes, we might consider trimming the input as part of comparisons, so
not simply invoke mpn_cmp.  (I think we should probably only compare a
with c and b with d, i.e., not speculate in that a and b or c and d
might be close.)

But we should do this like this IMO:

1. check signs and conditionally exit
2. count bits (split into grude limb count and finer bit count as now)
   and conditionally exit
3. compare + chop, exit iff denominators are equal
4. make a single-limb cross product, exit if difference is large enough
   to make the call here
5. perhaps perform some determinish computations (but I'm unsure about
   the utility of this); this might terminate in rare cases but will
   else reduce operands for the next step
5. perform either a gradually greater cross product or go for the full
   cross product right away

We might swap 3 and 4, since 3 is not O(1).  And "chop" should not be
taken literally; one needs to do the proper operand updates which means
subtraction of an operand pair.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list