OMEGA(log log(1/epsilon)) LOWER BOUND FOR APPROXIMATING THE SQUARE ROOT

Date
1989-10-01
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Computer Science
Citation