speed of unbalanced division

[Zimmermann Paul]

       Hi,

> 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.

Paul

PS: thanks for the patch, will try it as soon as possible