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

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.