Leo Liberti, James Ostrowski
Journal of Global Optimization
We prove an Ω(log log(1/ε)) lower bound on the depth of any computation tree and any RAM program with operations {+, -, *, /, ⌊·⌋, not, and, or, xor}, unlimited power of answering YES/NO questions, and constants {0,1} that computes √x to accuracy ε, for all x ∈ [1,2]. Since the Newton method achieves such an accuracy in O(log log(1/ε)) depth, our bound is tight. © 1997 Published by Elsevier Science B.V.
Leo Liberti, James Ostrowski
Journal of Global Optimization
Rolf Clauberg
IBM J. Res. Dev
Elena Cabrio, Philipp Cimiano, et al.
CLEF 2013
Yvonne Anne Pignolet, Stefan Schmid, et al.
Discrete Mathematics and Theoretical Computer Science