Name
Abstract | ||
|---|---|---|
We prove an \Omega\Gamma/17 log(1=")) lower bound on the depth of any computation tree andany RAM program with operations f+; \Gamma; ; =; b\Deltac ; not; and; or; xorg, unlimited power ofanswering YES/NO questions, and constants f0; 1g that computespx to accuracy ", for allx 2 [1; 2]. Since Newton method achieves such an accuracy in O(log log(1=")) depth, ourbound is tight.1 IntroductionIn this paper consider the problem of approximating the square root of a given number upto... |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0020-0190(97)00126-9 | Inf. Process. Lett. |
Keywords | Field | DocType |
square root,newton method,lower bound | Log-log plot,Discrete mathematics,Combinatorics,Upper and lower bounds,Square root,Computation tree,Mathematics,Computational complexity theory,Newton's method | Journal |
Volume | Issue | ISSN |
63 | 4 | 0020-0190 |
Citations | PageRank | References |
1 | 0.37 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nader H. Bshouty | 1 | 1171 | 126.09 |
| Yishay Mansour | 2 | 6211 | 745.95 |
| Baruch Schieber | 3 | 2647 | 320.36 |
| Prasoon Tiwari | 4 | 592 | 96.81 |