GMP 4.4 remaining tasks

[Paul Zimmermann]

       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