speed of unbalanced division

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> I expect it to quite simple to greatly improve the situation with some
> analysis. To get the curves perfectly smooth might require more work.

I think a reasonable strategy would be to check if qn < dn, and in that
case drop the low dn - qn - 1 limbs from both u and d when computing the
quotient. And then do a final adjustment including all limbs. I think
this should be applied to all sizes, except for small enough sizes that
all subroutines are quadratic.

Since one is going to need an adjustment step anyway, it might make
sense to use mpn_divappr to compute the quotient, and then do a final
adjustment including all limbs, but if one goes in that direction
optimal thresholds might get more complicated.

Regards,
/Niels

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