Division call in mpn_gcd
tg at gmplib.org
Fri Feb 24 13:27:36 CET 2012
nisse at lysator.liu.se (Niels Möller) writes:
You're right that the quotient is not wanted, mpn_div_r would make more
sense, but that function doesn't exist.
Indeed it doesn't. Nor does bdiv_r (for independent dividend and
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.
Except that redc does not accept independent sizes. Therefore we need
to use bdiv_qr.
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
Or perhaps slightly differently:
1. Drop trailing zeros of v, keep the count as vcnt
2. If u is even, drop its trailing zeros (might be lazy about that, only
dropping <= vcnt zeros to save time in this part and keep u > v
(approximatively u > v, I know this is not the precice mpn_gcd args
criteria) but I think that's sub-optimal.
3. Now, if u < v swap them (this can only happen if we dropped all u
4. Your point 3. Which thresholds are you talking about?
More information about the gmp-devel