A tight bound for approximating the square root

Nader H. Bshouty; Yishay Mansour; Baruch Schieber; Prasoon Tiwari

doi:10.1016/s0020-0190(97)00126-9

A tight bound for approximating the square root

Nader H. Bshouty
, Yishay Mansour
, Baruch Schieber
, Prasoon Tiwari

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

We prove an Ω(log log(1/ε)) lower bound on the depth of any computation tree and any RAM program with operations {+, -, *, /, ⌊·⌋, not, and, or, xor}, unlimited power of answering YES/NO questions, and constants {0,1} that computes √x to accuracy ε, for all x ∈ [1,2]. Since the Newton method achieves such an accuracy in O(log log(1/ε)) depth, our bound is tight.

Original language	English (US)
Pages (from-to)	211-213
Number of pages	3
Journal	Information Processing Letters
Volume	63
Issue number	4
DOIs	https://doi.org/10.1016/s0020-0190(97)00126-9
State	Published - Aug 28 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/s0020-0190(97)00126-9

Cite this

@article{163808fd3c1749569556120f1ac89b1e,

title = "A tight bound for approximating the square root",

abstract = "We prove an Ω(log log(1/ε)) lower bound on the depth of any computation tree and any RAM program with operations \{+, -, *, /, ⌊·⌋, not, and, or, xor\}, unlimited power of answering YES/NO questions, and constants \{0,1\} that computes √x to accuracy ε, for all x ∈ [1,2]. Since the Newton method achieves such an accuracy in O(log log(1/ε)) depth, our bound is tight.",

author = "Bshouty, \{Nader H.\} and Yishay Mansour and Baruch Schieber and Prasoon Tiwari",

year = "1997",

month = aug,

day = "28",

doi = "10.1016/s0020-0190(97)00126-9",

language = "English (US)",

volume = "63",

pages = "211--213",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - A tight bound for approximating the square root

AU - Bshouty, Nader H.

AU - Mansour, Yishay

AU - Schieber, Baruch

AU - Tiwari, Prasoon

PY - 1997/8/28

Y1 - 1997/8/28

N2 - We prove an Ω(log log(1/ε)) lower bound on the depth of any computation tree and any RAM program with operations {+, -, *, /, ⌊·⌋, not, and, or, xor}, unlimited power of answering YES/NO questions, and constants {0,1} that computes √x to accuracy ε, for all x ∈ [1,2]. Since the Newton method achieves such an accuracy in O(log log(1/ε)) depth, our bound is tight.

AB - We prove an Ω(log log(1/ε)) lower bound on the depth of any computation tree and any RAM program with operations {+, -, *, /, ⌊·⌋, not, and, or, xor}, unlimited power of answering YES/NO questions, and constants {0,1} that computes √x to accuracy ε, for all x ∈ [1,2]. Since the Newton method achieves such an accuracy in O(log log(1/ε)) depth, our bound is tight.

UR - https://www.scopus.com/pages/publications/0031213277

UR - https://www.scopus.com/pages/publications/0031213277#tab=citedBy

U2 - 10.1016/s0020-0190(97)00126-9

DO - 10.1016/s0020-0190(97)00126-9

M3 - Article

AN - SCOPUS:0031213277

SN - 0020-0190

VL - 63

SP - 211

EP - 213

JO - Information Processing Letters

JF - Information Processing Letters

IS - 4

ER -

A tight bound for approximating the square root

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this