Abstract
We prove an $OMEGA$(loglog(1/$epsilon$)) lower bound on the depth of any
computation tree and any RAM program with operations
{$+, -, *, /, left floor cdot right floor, not, and, or, xor$}, unlimited
power of answering YES/NO questions, and constants {0,1} that computes
$sqrt x$ to accuracy $epsilon$, for all $x \(mo $ [1,2]. Since Newton
method achieves such an accuracy in $O$(loglog(1/$epsilon$)) depth,
our bound is tight.
Notes
We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.ca
