Michael Ray, Yves C. Martin
Proceedings of SPIE - The International Society for Optical Engineering
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.
Michael Ray, Yves C. Martin
Proceedings of SPIE - The International Society for Optical Engineering
Thomas M. Cheng
IT Professional
Kafai Lai, Alan E. Rosenbluth, et al.
SPIE Advanced Lithography 2007
Thomas M. Cover
IEEE Trans. Inf. Theory