Bshouty, Nader H.2008-05-262008-05-261989-10-01http://hdl.handle.net/1880/46599In [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.EngComputer Scienceunknown1989-367-2910.11575/PRISM/30481