Complexity of approximating the square root

Yishay Mansour, Baruch Schieber, Prasoon Tiwari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages325-330
Number of pages6
ISBN (Print)0818619821, 9780818619823
DOIs
StatePublished - 1989
Externally publishedYes
Event30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA
Duration: Oct 30 1989Nov 1 1989

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Conference

Conference30th Annual Symposium on Foundations of Computer Science
CityResearch Triangle Park, NC, USA
Period10/30/8911/1/89

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Complexity of approximating the square root'. Together they form a unique fingerprint.

Cite this