GMP 4.4 remaining tasks

[Paul Zimmermann]

       Hi,

> >   From the work on single-limb inverses (invert_limb, see Alg. 2 and 3 in
> >   http://www.lysator.liu.se/~nisse/archive/draft-division-paper.pdf), I
> >   suspect that it is very difficult to get an "exact" reciprocal
> >   floor((B^{2n} - 1) / X) without an expensive multiplication at the end.
> >
> > Define "expensive multiplication".  For the single-limb case, an extra
> > limb multiplication is "expensive".  For the n-limb case, the result
> > should be possible to adjust in time O(n).
> 
> We should try the "add a virtual limb" strategy... But if you have the
> "exact or one unit too small" result and want to correct it... I suspect
> that you need an expensive nxn multiplication...

please keep in mind that in the worst-case, when dividing a n-bit number by
another n-bit number, the number of consecutive zeros or ones after the
rounding bit (i.e., after the first n+1 bits of the result) can be as large
as n-1 (same for the reciprocal). See for example:

@InProceedings{LaMu01,
  author =       {Tomas Lang and Jean-Michel Muller},
  title =        {Bounds on Runs of Zeros and Ones for Algebraic Functions},
  booktitle =    {Proceedings of the 15th IEEE Symposium on Computer Arithmetic (ARITH-15)},
  pages =        {13--20},
  year =         2001,
  publisher =    {IEEE Computer Society}
}

This means that unless one computes a 2n-bit (approximate) reciprocal, there
will be some cases where some extra computation is needed.

Paul