Division call in mpn_gcd

Torbjorn Granlund tg at gmplib.org
Fri Feb 24 10:55:47 CET 2012


Inspired by Marc{,o}'s cleanup commits, I decided to look for TMP_ALLOC*
calls that should be made into TMP_SALLOC* or TMP_BALLOC*.  Then I
spotted this unrelated thing:

  tp = TMP_ALLOC_LIMBS(talloc);

  if (usize > n)
    {
      mpn_tdiv_qr (tp, up, 0, up, usize, vp, n);

      if (mpn_zero_p (up, n))
	{
	  MPN_COPY (gp, vp, n);
	  ctx.gn = n;
	  goto done;
	}
    }

Why is mpn_tdiv_qr used here, the quotient should be irrelevent?  I'd
say to use mpn_bdiv_qr instead, to streamline things (followed by a
right shift to get rid of low zeros)?

After all, if g=gcd(a,b) then g | a and g | b, and g | (a + b*c) for any
a,b,c in Z.

-- 
Torbjörn


More information about the gmp-devel mailing list