GMP 4.4 remaining tasks

bodrato at mail.dm.unipi.it bodrato at mail.dm.unipi.it
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 :-)

Regards,
Marco

-- 
http://bodrato.it/



More information about the gmp-devel mailing list