gcdext_1 questions
Paul Zimmermann
Paul.Zimmermann at loria.fr
Thu Dec 3 23:08:25 CET 2009
Niels,
> 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.
Paul
More information about the gmp-devel
mailing list