GMP 4.4 remaining tasks

[Paul Zimmermann]

       Dear Marco,

> Uhm... Paul, are you around there?

yes I am!

> > I haven't looked closely neither at your code or at left-to-right
> > inversion in general. But maybe you can get some ideas from Alg 3.5
> > ApproximateReciprocal (page 121 in version 0.4) in Brent's and
> > Zimmermann's MCA book?
> 
> The lemma immediately _before_ that algorithm descriptions says:
> "Algorithm ApproximateReciprocal satisfies:
>                      AX < B^2n < A(X + 2)."
> The Proof immediately _after_ declare:
> "In all cases we have AX < B^2n < A(X + 1)"

this is for the base case only (n <= 2), where "In all cases" means both
for A = B^n/2 and A > B^n/2 (but both for n=2). I will make that clearer.
You can replace the bound n <= 2 in step 1 by any bound, as long as the
result ensures AX < B^2n < A(X + 2).

> If the condition is "B^2n < A(X+2)", then my implementation _is_ correct
> (the approximation is good enough :-). If we need "B^2n < A(X+1)", then I
> have to work on it.
> 
> Which condition should the result satisfy?

the result satisfies AX < B^2n < A(X + 2). I was unable to get a stricter
bound. The main reason is that in the recursive call (step of Alg. 3.5)
one considers a *truncated* part of the full input A.

Paul