Division call in mpn_gcd
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