Marco Bodrato bodrato at mail.dm.unipi.it
Sat Aug 17 09:17:50 UTC 2019


Il Sab, 17 Agosto 2019 9:15 am, Niels Möller ha scritto:
> nisse at 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

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...


More information about the gmp-devel mailing list