A TIGHT BOUND FOR APPROXIMATING THE SQUARE ROOT

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.