gcdext_1 questions

[Paul Zimmermann]

       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