Torbjorn Granlund <t...@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. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
