GMP 4.4 remaining tasks
Paul Zimmermann
Paul.Zimmermann at loria.fr
Mon Dec 7 14:08:28 CET 2009
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
More information about the gmp-devel
mailing list