Division call in mpn_gcd

[Niels Möller]

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?

  REDC_1_TO_REDC_2_THRESHOLD
  REDC_2_TO_REDC_N_THRESHOLD

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

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.

Regards,
/Niels

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