OMEGA(log log(1/epsilon)) LOWER BOUND FOR APPROXIMATING THE SQUARE ROOT
Date
1989-10-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In [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.
Description
Keywords
Computer Science