gcd_11
Niels Möller
nisse at lysator.liu.se
Sat Aug 17 10:42:48 UTC 2019
"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.
More information about the gmp-devel
mailing list