bdiv vs redc

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> What you're suggesting, is, I suppose:
>
> 1. Implement mpn_bdiv_r (at SB level, DC level, MU level)
>
> 2. Get rid of specific mpn_redc_* and use mpn_bdiv_r instead

Exactly, it would be nice if it could be reorganized this way.

> It would be trivial to fix at least mpn_sbpi1_bdiv_qr to pt the
> remainder in the low end.  It probably makes some sense.

It doesn't look entirely trivial to me, in the unbalanced case. In
general, of one does a redc in several steps (in the unbaanced qn > dn
case, the schoolbook (sb) code uses a loop reducing dn limbs at a time,
and the divide-and-conquer (dc) code also works in several iterations),
I think it will be inconvenient to get the remainder anywhere but at the
high end of the U area.

One simple way would be to define mpn_bdiv_r_n and mpn_bdiv_qr_n
(balanced division) with an additional rp input. This pointer would be
allowed to point at the low or high half of U (or to any non-overlapping
area). This would work fine at least for sb, not sure how easy it is for
dc. This could be a common building block for both redc and unbalanced
bdiv.

> Or perhaps we allow the quotient to be stored there?

No. That area is used for temporary storage for the addmul_1 carry
limbs. And this optimization is also the reason why the sb code operates
in blocks of size dn: After doing dn limbs, adding in the the carry
limbs cannot be delayed any longer.

> There should be a mpn_preinv_mu_bdiv_qr (we have the analogous Euclidian
> division function).  That would cover the current redc_n, but also allow
> for smaller pre-inverses for when the divisor/modulus invariance is
> smaller.

Makes sense. I'm not familiar with that interface.

Regards,
/Niels

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