Division call in mpn_gcd

Niels Möller nisse at lysator.liu.se
Fri Feb 24 11:44:39 CET 2012

Torbjorn Granlund <tg at gmplib.org> writes:

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

> Why is mpn_tdiv_qr used here, the quotient should be irrelevent?

You're right that the quotient is not wanted, mpn_div_r would make more
sense, but that function doesn't exist.

> I'd say to use mpn_bdiv_qr instead, to streamline things (followed by
> a right shift to get rid of low zeros)?

We don't require that v is odd (maybe it was a mistake to drop that
requirement?). So to use any bdiv funtions, we'd first have to deal with
powers of two upfront. And the quotient is still not needed, so I think
one would want to use bdiv_r, aka redc.

So I think the right method is:

1. In case both u and v are even, do needed book-keeping for the power
   of two in the gcd.

2. Drop trailing zeros of v.

3. Reduce the size of u using redc. Unlike the use in powm, there's no
   amortization of the inverse computation, so we may need new


Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

More information about the gmp-devel mailing list