A TIGHT BOUND FOR APPROXIMATING THE SQUARE ROOT
Date
1995-05-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We prove an $OMEGA$(loglog(1/$epsilon$)) lower bound on the depth of any
computation tree and any RAM program with operations
{$+, -, *, /, left floor cdot right floor, not, and, or, xor$}, unlimited
power of answering YES/NO questions, and constants {0,1} that computes
$sqrt x$ to accuracy $epsilon$, for all $x \(mo $ [1,2]. Since Newton
method achieves such an accuracy in $O$(loglog(1/$epsilon$)) depth,
our bound is tight.
Description
Keywords
Computer Science