A tight bound for approximating the square root

✍ Scribed by Nader H. Bshouty; Yishay Mansour; Baruch Schieber; Prasoon Tiwari

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 285 KB
• Volume: 63
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00126-9

✦ Synopsis

We prove an R (log log( l/c) ) lower bound on the depth of any computation tree and any RAM program with operations {+, -, *, /, [.j, not, and, br, xor}, unlimited power of answering YES/NO questions, and constants (0.1) that computes 4 to accuracy E, for all x E [ 1,2]. Since the Newton method achieves such an accuracy in 0( log log( 1 /e) ) depth, our bound is tight.