Ciao, Il Sab, 17 Agosto 2019 9:15 am, Niels Möller ha scritto: > ni...@lysator.liu.se (Niels Möller) writes: > >> Seems to work, but not particularly fast :-( > > And I think I understand why... I think progress for a gcd algorithm > like this needs to be measured in terms of bitsize (a) + bitsize (b), > not bitsize (max (a,b)).
> I now think that any efficient iteration for small-size gcd ought to > care which one of a, b is smallest, and make it impossible or very > unlikely that the iteration makes min(a,b) grow. Well, the smallest is a candidate result, so I agree, it should never be lost. 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... With |u-v|/2 we surely gain one bit because of the division, and maybe we gain something more thanks to cancellation of the highest bits. 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... Ĝis, m _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
