nisse at lysator.liu.se
Thu Dec 3 23:22:47 CET 2009
Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:
> If you consider instead the "binary recursive gcd" we defined with
> Damien Stehlé, it removes 1.95 bit per iteration.
I haven't considered this for small sizes (at least not for some years,
I don't remember if I looked into that when I implemented it the
subquadratic algorithm for large integers, where my implementation was
10% slower than the left-to-right algorithm).
The basic iteration would be count_trailing_zeros, shift, table lookup
to get an inverse (and an unlikely newton iteration if there are many
bits), a multiply to get the quotient, and another multiply and shift to
get the remainder.
But it's not clear to me what book-keeping and postprocessing is needed
to get cofactors according to the required conventions.
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel