article

Free access

The logarithmic error and Newton's method for the square root

Authors:

Richard F. King,

David L. PhillipsAuthors Info & Claims

Communications of the ACM, Volume 12, Issue 2

Pages 87 - 88

https://doi.org/10.1145/362848.362861

Published: 01 February 1969 Publication History

PDF eReader

Abstract

The problem of obtaining optimal starting values for the calculation of the square root using Newton's method is considered. It has been pointed out elsewhere that if relative error is used as the measure of goodness of fit, optimal results are not obtained when the inital approximation is a best fit. It is shown here that if, instead, the so-called logarithmic error is used, then a best initial fit is optimal for both types of error. Moreover, use of the logarithmic error appears to simplify the problem of determining the optimal initial approximation.

References

[1]

MOURSUND, DAVID G. Optimal starting values for Newton- Raphson calculation of x. Comm. ACM 10, 7 (July 1967), 430-432.

Digital Library

Google Scholar

[2]

MAEHLY, HANS J. Approximations for the Control Data 1604, Ch. 1. Approximations for the square root, Proj: N.R. 044.196, Princeton U., Princeton, N.J., Jan. 1960, pp. 3-11.

Google Scholar

[3]

CODY, W.J. Double-precision square root for the CDC-3600. Comm. ACM 7, 12 (Dec. 1964), 715-718.

Digital Library

Google Scholar

[4]

KING, RICHARD. On the double-precision square root routine. Comm. ACM 8, 4 (Apr. 1965), 202. (Letter to the Editor)

Google Scholar

[5]

MOURSUND, D. G. Computational aspects of Chebyshev approximation using a generalized weight function. SIAM J. Numer. Anal. 5, 1 (Mar. 1968), 126--137.

Google Scholar

[6]

AND TAYLOR, G. D. Optimal starting values for the Newton-Raphson calculation of inverses of certain functions. SIAM J. Numer. Anal. 5,1 (Mar, 1968), 138-150.

Google Scholar

Cited By

View all

Lee JSull S(2019)Regression Tree CNN for Estimation of Ground Sampling Distance Based on Floating-Point RepresentationRemote Sensing10.3390/rs1119227611:19(2276)Online publication date: 29-Sep-2019
https://doi.org/10.3390/rs11192276
Rousan NAbu-Salem HBryant BLamont GHaddad HCarroll J(1999)Computation of √xProceedings of the 1999 ACM symposium on Applied computing10.1145/298151.298198(74-77)Online publication date: 28-Feb-1999
https://dl.acm.org/doi/10.1145/298151.298198
Kwan HNelson RSwartzlander E(1995)Cascaded implementation of an iterative inverse-square-root algorithm, with overflow lookaheadProceedings of the 12th Symposium on Computer Arithmetic10.1109/ARITH.1995.465369(115-122)Online publication date: 1995
https://doi.org/10.1109/ARITH.1995.465369
Show More Cited By

Index Terms

The logarithmic error and Newton's method for the square root
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis
      1. Approximation
    2. Nonlinear equations
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

Minimax logarithmic error

In this note we point out how rational approximations which are best with respect to maximum logarithmic error can be computed by existing algorithms. Let y be a quantity that we wish to approximate and y be an approximation, then the logarithmic error ...
Applications of the Cosecant and Related Numbers

Power series expansions for cosecant and related functions together with a vast number of applications stemming from their coefficients are derived here. The coefficients for the cosecant expansion can be evaluated by using: (1) numerous recurrence ...
The complexity of approximating the square root
SFCS '89: Proceedings of the 30th Annual Symposium on Foundations of Computer Science

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 12, Issue 2

Feb. 1969

55 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/362848

Editor:
M. Stuart Lynn
IBM Scientific Center, Houston, TX

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 1969

Published in CACM Volume 12, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
1,155
Total Downloads

Downloads (Last 12 months)94
Downloads (Last 6 weeks)10

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lee JSull S(2019)Regression Tree CNN for Estimation of Ground Sampling Distance Based on Floating-Point RepresentationRemote Sensing10.3390/rs1119227611:19(2276)Online publication date: 29-Sep-2019
https://doi.org/10.3390/rs11192276
Rousan NAbu-Salem HBryant BLamont GHaddad HCarroll J(1999)Computation of √xProceedings of the 1999 ACM symposium on Applied computing10.1145/298151.298198(74-77)Online publication date: 28-Feb-1999
https://dl.acm.org/doi/10.1145/298151.298198
Kwan HNelson RSwartzlander E(1995)Cascaded implementation of an iterative inverse-square-root algorithm, with overflow lookaheadProceedings of the 12th Symposium on Computer Arithmetic10.1109/ARITH.1995.465369(115-122)Online publication date: 1995
https://doi.org/10.1109/ARITH.1995.465369
Hall L(1989)Beyond the Standard ModelXXIV International Conference on High Energy Physics10.1007/978-3-642-74136-4_17(335-356)Online publication date: 1989
https://doi.org/10.1007/978-3-642-74136-4_17
Meinardus GTaylor G(1980)Optimal partitioning of Newton’s method for calculating rootsMathematics of Computation10.1090/S0025-5718-1980-0583499-535:152(1221-1230)Online publication date: 1980
https://doi.org/10.1090/S0025-5718-1980-0583499-5
Dunham C(1979)Weighted Chebyshev approximation on a compact Hausdorff spaceAequationes Mathematicae10.1007/BF0218986319:1(151-159)Online publication date: Dec-1979
https://doi.org/10.1007/BF02189863
Andrews MMcCormick STaylor GGosden JJohnson O(1976)Evaluation of the square root function on microprocessorsProceedings of the 1976 annual conference10.1145/800191.805571(185-191)Online publication date: 20-Oct-1976
https://dl.acm.org/doi/10.1145/800191.805571
Gibson J(1974)Optimal rational starting approximationsJournal of Approximation Theory10.1016/0021-9045(74)90047-112:2(182-198)Online publication date: Oct-1974
https://doi.org/10.1016/0021-9045(74)90047-1
Meinardus GTaylor G(1973)Optimal starting approximations for iterative schemesJournal of Approximation Theory10.1016/0021-9045(73)90108-19:1(1-19)Online publication date: Sep-1973
https://doi.org/10.1016/0021-9045(73)90108-1
Reingold E(1972)Establishing lower bounds on algorithmsProceedings of the May 16-18, 1972, spring joint computer conference10.1145/1478873.1478936(471-481)Online publication date: 16-May-1972
https://dl.acm.org/doi/10.1145/1478873.1478936
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Minimax logarithmic error

Applications of the Cosecant and Related Numbers

The complexity of approximating the square root

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations