Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/45753
Title: A TIGHT BOUND FOR APPROXIMATING THE SQUARE ROOT
Authors: Bshouty, N.
Mansour, Y.
Tiwari, P.
Schieber, B.
Keywords: Computer Science
Issue Date: 1-May-1995
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.
URI: http://hdl.handle.net/1880/45753
Appears in Collections:Bshouty, Nader

Files in This Item:
File Description SizeFormat 
1995-570-22.pdf514.05 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.