General mpn_gcd_basecase

[Niels Möller]

"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:

> Sounds more interesting than binary euclid, to me. Because looking at the
> lowest bits and just detecting the bit size seems easier than extracting
> the highest bits each loop.

But it doesn't matter that much in which end bits are eliminated. Assume
u,v odd, u > v, and we look for an update replacing u <-- u - q v.

If u and v are the same bitsize, then u <-- u - v clears a bit in each
end, and I don't think we can do much better, e.g, using u + v when that
clears two bits at the low end seems to not gain much, since compared to
u - v we lose about as much at the high end.

If u is one bit larger than v, then plain euclid makes one bit of
progress, while binary euclid makes two bits progress. Binary algorithm
choosing between u-v and u+v also makes almost two bits of progress
(worst case is when we use u+v and get a carry out.

If u is two bits larger than v, then binary euclid makes three bits of
progress, with q chosen from {3, 5, 7}. We can also make 3 bits of
progress by setting q = -u v^{-1} (mod 8) with representatives from the
set {±1, ±3}

If u is k bits larger than v, k "large", then one can make k+1 bits of progress
by a full euclidean or mod 2^{k+1} division. What Torbjörn suggests, I
think, is to get a multiplier q' = u v^{-1} (mod 2^j) with j = 4 or so by table
lookup, and then set q = 2^k + q'. Then we cancel j bits at the low end
and 1 bit at the high end.

My gut feeling is that it's not so useful to do something very clever
for the case that k, the bit size difference between u and v, is large.
It's a fairly unlikely case, we make decent progress if we just use the
2^j-sized table and get j bits of progress per iteration, and when the
difference is large enough, it will pay off to just do a division
operation (of either kind) producing a full k-bit quotient.

Regards,
/Niels

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