mpn_gcd[ext] interface details

Torbjorn Granlund tg at gmplib.org
Tue May 10 16:50:53 CEST 2011


nisse at lysator.liu.se (Niels Möller) writes:

  nisse at lysator.liu.se (Niels Möller) writes:
  
  > I've tried to clarify the mpz_gcdext documentation now. Feel free to
  > double check that the conditions on S and T make sense (including the
  > borderline cases where one or both inputs are zero). I also edited the
  > description of mpz_gcd, to document that we define gcd(0,0) = 0.
  
  And what about normalization of the inputs? The mpn_gcdext documentation
  says nothing about normalization. The documentation for mpn_gcd says
  that both inputs must be normalized.
  
  I think the actual requirements for both functions are something like
  
    * an < bn is not allowed
  
    * if an == bn, then at least one of a or b must be normalized.
  
    * if an > bn, then b must be normalized
  
  In particular, a > b seems not to be necessary in all cases.
  
  What should the documented requirements be?
  
I would suggest that we demand A >= B, and that B is normalised.

What exact normalisation requirements does the present code have,
bp[bn-1] != 0, or stricter?

It does make sense to allow some freedom to make the code more strict in
the future.  Also, there is a value in keeping the interface simple; the
exact rules you describe are a bit more involved that I think we should
document.

I checked the 4.2.1 manual (available at
http://gmplib.org/manual-4.2.1/Low_002dlevel-Functions.html) and no
normalisation requirements are documented.

Did we actually break backwards compatibility at some point?

-- 
Torbjörn


More information about the gmp-devel mailing list