Range for the coeffients returned by gcdext

Niels Möller nisse at lysator.liu.se
Thu Oct 2 22:42:53 CEST 2003

Kevin Ryde <user42 at zip.com.au> writes:

> Torbjorn Granlund <tege at swox.com> writes:
> >
> > Please don't specify something just for the uniformity of mpn.
> > Uniformity isn't an important design goal of mpn.  Speed, though,
> > is.

A liberal specification could be that gcdext(a,b), with a, b > 0,
should return numbers g, u such that

  g = u a + v b = gcd(a, b) > 0
  |u| <= b

I think the spec for gcdext should provide some limit for the size of
u, even if it doesn't specifiy u uniquely.


More information about the gmp-devel mailing list