gcd_11

[Niels Möller]

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

> Moreover... if u and v has more or less the same size, then u+3v is around
> 4u, even if we can divide it by 8... well, we obtain something around u/2,
> we gained just one bit...

And if u and v are close enough in size,, then |u - v| cancels bits at
*both* ends. Which can be generalized to the "euclidean binary"
algorithm,

  q = u / v;
  q |= 1;    /* Make it odd */
  u = abs(u - q*v)
  divide out power of twos from u.

To do that efficiently, we'de need a table lookup of the most
significant bits of u amd v, rather than the least significant bits; if
they're enough to get the right q, great, we make good progress at both
ends. If not, we can fall back to q = 1 and an iteration of plain
binary.

> If v << u, then it is probably better to explore u-3v or even larger
> multiple of v... but maybe this exploration is not much more efficient
> than the current loop...

Stehlé-Zimmermann binary gcd does about that, choosing a hensel/2-adic
quotient of size matching the difference in bitsize between u and v. But
it seems using a too large quotient doesn't cause any harm; it's just
that you don't get more progress than with the appropate smaller
quotient. Which I think is why Torbjörn's table based code makes good
progress, when using large quotients.

Regards,
/Niels

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