Properly rounded variable precision square root

ABSTRACT

The square root function presented here returns a properly rounded approximation to the square root of its argument, or it raises an error condition if the argument is negative. Properly rounded means rounded to the nearest, or to nearest even in case of a tie. It is variable precision in that it is designed to return a p-digit approximation to a p-digit argument, for any p > 0. (Precision p means p decimal digits.) The program and the analysis are valid for all p > 0, but current implementations place some restrictions on p.

REFERENCES

• 1: BRZNT, R.P. Unrestricted algorithms for elementary and special functions. In Proceedings of the IFIP Congress 80 (Tokyo and Melbourne, Oct. 1980), Simon Livingston (Ed.), North Holland, Amsterdam, 1980, 613-619.
• 2: CLENSHAW, C. W. AND OLIVER, F. W.J. An unrestricted algorithm for the exponential function. SIAM J. Numer. Anal., 17, 2 (1980), 310-331.
• 3: William James Cody, Software Manual for the Elementary Functions (Prentice-Hall series in computational mathematics), Prentice-Hall, Inc., Upper Saddle River, NJ, 1980
• 4: COHEN, M. S., HULL, T. E. AND HAMACHER, V.C. CADAC: A controlled-precision decimal arithmetic unit. IEEE Trans. Comput. C-32, 4 (Apr. 1983), 370-377.
• 5: R C. Holt , J N.P Hume, Introduction to computer science using the TURING programming language, Reston Publishing Co., Reston, VA, 1984
• 6: HULL, T.E. The use of controlled precision. In Proceedings of the IFIP TC2 Working Conference on the Relationship between Numerical Computation and Programming Languages (Boulder, Colo., Aug. 1981), J. K. Reid (Ed.), North-Holland, Amsterdam (1982), 71-84.
• 7: T. E. Hull , A. Abrham , M. S. Cohen , A. F. X., Curley , C. B. Hall , D. A. Penny , J. T. M., Sawchuk, Numerical Turing, ACM SIGNUM Newsletter, v.20 n.3, p.26-34, July 1985 [doi>10.1145/1057947.1057949]
• 8: John Reid, Functions for manipulating floating-point numbers, ACM SIGNUM Newsletter, v.14 n.4, p.11-13, December 1979 [doi>10.1145/1057514.1057515]

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms; Error analysis
      G.1.2 Approximation
          Subjects: Elementary function approximation
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis; Verification**; Certification and testing

General Terms:
Algorithms, Verification

Keywords:
correctness proof, variable precision