Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/46599
Title: OMEGA(log log(1/epsilon)) LOWER BOUND FOR APPROXIMATING THE SQUARE ROOT
Authors: Bshouty, Nader H.
Keywords: Computer Science
Issue Date: 1-Oct-1989
Abstract: In [FOCS 89], Mansour-Schieber-Tiwari proved that any computation tree with the operations {+, -, times, /, \(lf \(rf, <} and constants {0,1} that computes sqrt x to accuracy epsilon, for all x \(mo [1,2], must have depth OMEGA ( sqrt {log log(1/ epsilon )}). In this paper we prove that any computation tree with operations {+, -, times, /, \(lf \(rf, <, NOT, AND, OR, XOR}, indirect addressing, unlimited power of answering YES/NO questions and constants {0,1} that computes sqrt x to accuracy epsilon for all x \(mo [1,2] must have depth OMEGA(log log(1/epsilon)). By Newton iteration our bound is tight.
URI: http://hdl.handle.net/1880/46599
Appears in Collections:Bshouty, Nader

Files in This Item:
File Description SizeFormat 
1989-367-29.pdf294.75 kBAdobe PDFView/Open


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