"Marco Bodrato" <bodr...@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. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
