GMP 4.4 remaining tasks
Paul Zimmermann
Paul.Zimmermann at loria.fr
Tue Dec 8 12:02:04 CET 2009
Niels,
> This is what we do for invert_limb. As I said, I'm afraid that achieving
> this requires an expensive adjustment at the end. But I think we can
> achieve the relaxed bound
>
> 0 < B^{2n} - AX <= A (1 + epsilon)
>
> for some fairly small epsilon, without needing any expensive adjustment.
> The MCA algorithm and proof gives us epsilon = 1, but I expect that one
> can get this down closer to 1/B by using an extra limb of precision at
> the right places.
this is easy to achieve. Simply add one word to A and X, which now become
A'=BA and X'=BX+r with 0 <= r < B, call Alg. 3.5, then you get:
0 < B^{2n+2} - A'X' < 2A'
which gives after division by B^2:
0 < B^{2n} - A(X+r/B) < 2A'/B^2
or:
0 < B^{2n} - AX < 2A/B + A r/B <= A (1 + 1/B)
Paul
More information about the gmp-devel
mailing list