Range for the coeffients returned by gcdext

[Torbjorn Granlund]

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
  absolutely necessary.
  
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
it.)

-- 
Torbjörn