Niels Möller nisse at lysator.liu.se
Sat Aug 17 07:15:59 UTC 2019

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

And then an iteration like the a' = a + kb, b' = a + mb considered here,
which always reduce max(a,b) but often increase min(a,b), is at a great

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.


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