TY - GEN

T1 - Complexity of approximating the square root

AU - Mansour, Yishay

AU - Schieber, Baruch

AU - Tiwari, Prasoon

PY - 1989

Y1 - 1989

N2 - The authors prove upper and lower bounds for approximately computing the square root using a given set of operations. The bounds are extended to hold for approximating the kth root, for any fixed k. Several tools from approximation theory are used to prove the lower bound. These include Markoff inequality, Chebyshev polynomials, and a theorem that relates the degree of a rational function to its deviation from the approximated function over a given interval. The lower bound can be generalized to other algebraic functions. The upper bound can be generalized to obtain an O(1)-step straight-line program for evaluating any rational function with integer coefficients at a given integer point.

AB - The authors prove upper and lower bounds for approximately computing the square root using a given set of operations. The bounds are extended to hold for approximating the kth root, for any fixed k. Several tools from approximation theory are used to prove the lower bound. These include Markoff inequality, Chebyshev polynomials, and a theorem that relates the degree of a rational function to its deviation from the approximated function over a given interval. The lower bound can be generalized to other algebraic functions. The upper bound can be generalized to obtain an O(1)-step straight-line program for evaluating any rational function with integer coefficients at a given integer point.

UR - http://www.scopus.com/inward/record.url?scp=0024772319&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024772319&partnerID=8YFLogxK

U2 - 10.1109/sfcs.1989.63498

DO - 10.1109/sfcs.1989.63498

M3 - Conference contribution

AN - SCOPUS:0024772319

SN - 0818619821

SN - 9780818619823

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 325

EP - 330

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - Publ by IEEE

T2 - 30th Annual Symposium on Foundations of Computer Science

Y2 - 30 October 1989 through 1 November 1989

ER -