gcdext_1 questions

Paul Zimmermann Paul.Zimmermann at loria.fr
Thu Dec 3 23:08:25 CET 2009


> Comments and suggestions are of course highly appreciated.

about Stein's binary gcd algorithm: on average it removes 1.42 bit per
iteration (cf Knuth vol2, 4.5.2). If you consider instead the "binary
recursive gcd" we defined with Damien Stehlé, it removes 1.95 bit per
iteration. You can do even better: in the binary division of our algorithm,
the quotient is centered in [-2^j, 2^j]. If instead you take a negative
quotient in [-2^{j+1}, 0] when both terms are of the same sign, and a positive
quotient in [0, 2^{j+1}] when the signs differ, you remove on average 2.20
bits per iteration.


More information about the gmp-devel mailing list