Division call in mpn_gcd
nisse at lysator.liu.se
Fri Feb 24 14:28:09 CET 2012
Torbjorn Granlund <tg at gmplib.org> writes:
> Except that redc does not accept independent sizes. Therefore we need
> to use bdiv_qr.
I think it should be easy to generalize at least redc_1 and redc_2 to
accept independent sizes. Might require some more work for redc_n, which
would need some kind of block-wise processing.
> 4. Your point 3. Which thresholds are you talking about?
Using bdiv_qr is surely an improvement, but I think we really ought to
have some division function which doesn't require storage for the
unwanted quotient. Should that function be bdiv_r, or redc, or even
div_r? IIRC, bdiv and redc have slightly different notions on what the
"remainder" is, but I imagine either variant would fine for the gcd
When un >> vn, gcd(u, v) shouldn't need O(un) scratch space (btw, this
calls for an initial reduction also in mpz_gcd).
There are a couple of other divisions in the gcd code where the quotient
is similarly unwanted: The initial division in mpn_gcdext, and the
(unlikely) division in mpn_gcd_subdiv_step. All these divisions have the
property that it doesn't really mattter if the remainder is a few bits
too large, so any final adjustment step can be omitted.
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel