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