Torbjorn Granlund <t...@gmplib.org> writes: > 2011-12-10 Torbjorn Granlund <t...@gmplib.org> > > * mpn/generic/sbpi1_bdiv_q.c: Delay quotient limb stores in order to > allow quotient and dividend to completely overlap. > * mpn/generic/sbpi1_bdiv_qr.c: Likewise. > > Perhaps it doesn't work, or does not always work (depending on relative > operand sizes).
I seriously doubt that it works for sbpi1_bdiv_qr. I think it does work for sbpi1_bdiv_q. That function doesn't use the trick of delaying the addition of the carry limbs, it just applies the carry limbs one at a time with mpn_add_1, like cy = mpn_addmul_1 (np, dp, dn, q); mpn_add_1 (np + dn, np + dn, i, cy); > I cannot remember what usage needed this change, it > might have been the new binomomial code. I did a quick search, without finding any users. > Don't exaggerate...! And what is "natural" is less important what makes > things smooth, we're talking mpn after all! Say we start with n = 20 limbs, uuuuuuuuuuuuuuuuuuuu (most significant limb to the left) and start with reducing by k = 4 < n limbs, at the low end. If the recursive bdiv operation puts the remainder in the high end, we get to uuuuuuuuuuuurrrr0000 which is the complete partial remainder and some trailing zeros. While if it is put at the low end, we get uuuuuuuuuuuu....rrrr where the partial remainder is split into two disjoint areas. Next step would be to apply the quotient to the untouched "u"-part of the partial remainder.Say we have a quotient of k = 4 limbs and the high part of d is also 4 limbs, then the product v = q * dh should be added in as uuuuuuuuuuuu....rrrr vvvv vvvv We can split the add into mpn_add_n and mpn_add_nc (if mpn_add_nc is available!), and move the upper part down in the process, to get uuuuuuuu....uuuurrrr I imagine it could work without much additional overhead, but it seems a bit messy and "non-smooth". 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