Bshouty, N.Mansour, Y.Tiwari, P.Schieber, B.2008-02-272008-02-271995-05-01http://hdl.handle.net/1880/45753We 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.EngComputer Scienceunknown1995-570-2210.11575/PRISM/30474