speed of unbalanced division
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