GMP 4.4 remaining tasks

bodrato at bodrato at
Mon Dec 7 12:48:28 CET 2009

... here I am again...

> 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)"

I did read the full proof, the "In all cases we have AX < B^2n < A(X + 1)"
refers _only_ to the initial (n<=2) step of the induction, where a
division is used.
The full (recursive or iterative) algorithm gives a result satisfying the
"+2" condition.
This means that my implementation was not completely wrong...
But I'll probably conform it to Algo 3.5... otherwise I should write a new
proof :-)

Thanks Niels for giving me the hint, and thanks Paul for publishing your
fine book on-line :-)



More information about the gmp-devel mailing list