speed of unbalanced division
Paul.Zimmermann at loria.fr
Wed Feb 6 21:28:42 CET 2013
> From: Torbjorn Granlund <tg at gmplib.org>
> Date: Tue, 05 Feb 2013 21:10:29 +0100
> nisse at lysator.liu.se (Niels Möller) writes:
> > 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?
> Good questions.
> The code for choosing 'in' today does not take dn into account, except
> that it make sure in <= dn holds. The main multiply, for generating
> quotient limbs, is always balanced. Then, as a result of the current
> 'in' choice, the 2nd multiply will typically be unbalanced. This is
> actually part of the mu algorithm idea, that 'in' is usually around
my intuition is that for qn > dn, choosing for k the smallest integer such that
qn/k <= dn should be close to optimal. In such a way one would do k-1 balanced
divisions with remainder, and one final balanced division without remainder.
PS: thanks for the patch, will try it as soon as possible
More information about the gmp-devel