Range for the coeffients returned by gcdext

Kevin Ryde user42 at zip.com.au
Fri Sep 19 10:17:39 CEST 2003

nisse at lysator.liu.se (Niels Möller) writes:
> So which representatives should be returned?

This question has been on the todo list for a while.  It might have
been Jason Moxham who first asked about it.

>   -(b-1)/2 <= u <= (b-1)/2  for odd b, and
>   -b/2 < u <= b/2           for even b

I'd been wondering if the usual Euclidean algorithm guaranteed that
already, or something like it, so all we would have to do is document
what the current code does :-).

The only thing to be careful of is not to specify something that might
be hard to implement in the future.  But I expect once one has u,v
roughly in the vicinity of a,b then any sensible rule can be applied
with not much work, certainly not much compared to getting there in
the first place.

More information about the gmp-devel mailing list