speed of unbalanced division

Niels Möller nisse at lysator.liu.se
Mon Feb 4 22:02:23 CET 2013

Torbjorn Granlund <tg at gmplib.org> writes:

> The qn > dn case is where the current code performs badly.

I see, I misunderstood. Then it's not as obvious. 

> The fix is choosing the inverse size less stupidly, and organising the
> computation in more similarly sized quotient blocks.

So there should be k blocks, of roughly qn/k limbs each. I have poor
intuition about this, should one choose (maximum?) k so that qn/k <= dn,
or does it ever make sense to copute an inverse of size larger than dn?


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

More information about the gmp-devel mailing list