Browsing by Author "Mansour, Y."
Now showing 1 - 1 of 1
Results Per Page
Sort Options
Item Open Access A TIGHT BOUND FOR APPROXIMATING THE SQUARE ROOT(1995-05-01) Bshouty, N.; Mansour, Y.; Tiwari, P.; Schieber, B.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.