speed of mpq_cmp vs mpq_sub

[Torbjörn Granlund]

Some more thoughts on this.  Consider a/b vs c/d.  Assume all are
non-negative for simplicity.

Once we have determined that a != c or b != d, we know a/b != c/d since
we require canonicalised input.

That means that we could develop the actual binary fraction a/b and c/d
bit for bit (or limb for limb, or limb-block for limb-block) until the
generated bits differ.

Why is this interesting?  Because it suggest an iterative algorithm
which on average would terminate very quickly.

Instead of actually computing fractional quotient bits, one could com-
pute the continued fractions in parallel, i.e., essentially two parallel
gcd ops.  (And one could then choose between computing cfrac(a,b) plus
cfrac(c,d) or else cfrac(a,c) plus cfrac(b,d).)

Somewhat similarly, one could do the cross-products blockwise top-to-
bottom, again nornally terminating early.  One would never need to
generate all product bits for both cross-products, since a difference
will occur before.



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