speed of unbalanced division

[Torbjorn Granlund]

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.

I think a GMP release that basically only tunes and refines what we
currently have implemented might make more improvement that most other
releases.

-- 
Torbjörn