speed of unbalanced division

Zimmermann Paul 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
> dn/2.

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 mailing list