gcd_11

[Niels Möller]

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

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.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.