Range for the coeffients returned by gcdext
tege at swox.com
Tue Sep 16 22:57:25 CEST 2003
nisse at lysator.liu.se (Niels Möller) writes:
So which representatives should be returned? It would make some sense
to always choose u such that 0 <= u < b.
That would make some sense.
So what is expected from mpz_gcdext and mpn_gcdext? I find it a little
odd that mpn_gcdext is documented as returning a positive or negative
u, but most other mpn functions deal with negative numbers only when
This is probably due to soemwhat sloppy thinking (on my part)
back when mpn_gcdext was introduced in gmp 2.0.
By the way, I think I've understood how to do binary gcdext (although
in the context of Schönhage's algorithm, I can use that only for the
one limb basecase):
Cool. I never understood it.
It would be interesting to see how that performs for 1, 2, 3, ...
limbs compared to the current O(n^2) code that relies on
division. (Yes, I am suggesting a mpn-level implementaion of
More information about the gmp-devel