GMP 4.4 remaining tasks
Paul Zimmermann
Paul.Zimmermann at loria.fr
Tue Dec 8 12:12:15 CET 2009
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
More information about the gmp-devel
mailing list