Division call in mpn_gcd

[Niels Möller]

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
   thresholds.

Regards,
/Niels

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