Automatic Controlled Precision Calculations

ABSTRACT

Recent developments in computer design and error analysis have made feasible the use of variable precision arithmetic and the preparation of programs that automatically determine their own precision requirements. Such programs enable the user to specify the accuracy he wants, and yield answers guaranteed to lie within the bounds prescribed. A class of such programs, called “contracting error programs,” is defined in which the precision is determined by prescribing error bounds on the data. A variant of interval arithmetic is defined which enables a limited class of algorithms to be programmed as contracting error programs. A contracting error program for the solution of simultaneous linear equations is described, demonstrating the application of the idea to a wider class of problems.

REFERENCES

• 1: R. L. Ashenhurst , N. Metropolis, Unnormalized Floating Point Arithmetic, Journal of the ACM (JACM), v.6 n.3, p.415-428, July 1959 [doi>10.1145/320986.320996]
• 2: ASHENHURST, R. L. The Maniac III arithmetic system. Proc. Spring Joint Comput. Conf. Vol. 21, 1962, pp. 195-202. National Press, Palo Alto, Calif.
• 3: ASHENHURST, R. L. Techniques for automatic error monitoring and control. In L. B. Rall (Ed.), Error in Digital Computation, Vol. I, pp. 43-59. John Wiley and Sons, New York, 1965.
• 4: ASHENHURST, R. L., AND METROPOLIS, N. Error estimation in computer calculation. Amer. Math. Mon. 74, 2 (Feb. 1965), Part 2 (supplement), Computers and Computing, No. 10 of the Herbert Slaught Memorial Papers series of the Mathematical Association of America, pp. 47-58.
• 5: ASHENHURST, R. L. Experimental investigation of unnormalized computation. Symp. on Error in Digital Comput., Madison, Wise., April 1965.
• 6: GRAY, L. H., AND HARRISON, J. C. Normalized floating point airthmetic with an index of significance. Proc. Eastern Joint Comput. Conf., Vol. 16, 1959, pp. 244-249. National Joint Computer Committee, 1959.
• 7: RICHTMTER, R. D. Power series solution, by machine, of a nonlinear problem in twodimentionsl fluid flow. Ann. N. Y. Acad. Sci. 86 (1960), 828-843.
• 8: W. G. Wadey, Floating-Point Arithmetics, Journal of the ACM (JACM), v.7 n.2, p.129-139, April 1960 [doi>10.1145/321021.321024]
• 9: Max Goldstein, Significance arithmetic on a digital computer, Communications of the ACM, v.6 n.3, p.111-117, March 1963 [doi>10.1145/366274.366339]
• 10: R. H. Miller, An example in “significant-digit” arithmetic, Communications of the ACM, v.7 n.1, p.21, Jan. 1964 [doi>10.1145/363872.363895]
• 11: MOORE, R. E. AND YANO, C. T. Interval analysis I. Tech. Doc. LMSD-285875, Lockheed Aircraft Corp., Missiles & Space Div., Sunnyvale, Calif. 1959.
• 12: MOORE, R. E. The automatic analysis and control of error in digital computing based on the use of interval numbers. In L. B. Rall (Ed.), Error in Digital Computation, Vol, I, pp. 61-130, John Wiley and Sons, New York, 1965.
• 13: MOORE, R. E. Automatic local coordinate transformations to reduce the growth of error bounds in interval computation of solutions of ordinary differential equations. Symp. on Error in Digital Computation, Madison, Wise., April 1965.
• 14: James H. Wilkinson, Rounding Errors in Algebraic Processes, Dover Publications, Incorporated, 1994
• 15: National Physical Laboratory, Notes on Applied Science, No. 16, Modern Computing Methods (2nd Ed.), Her Majesty's Stationary Office, London, 1961.
• 16: Allan Gibb, Algorithm 61: procedures for range arithmetic, Communications of the ACM, v.4 n.7, p.319-320, July 1961 [doi>10.1145/366622.366637]
• 17: CHARTRES, B. A. Controlled precision calculations and the Danilewski method. Rep. IBM-E-148/8, NSF-E-872, Div. Appl. Math., Brown U., Providence, R. I., Mar. 1964

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Computer arithmetic

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Error analysis

General Terms:
Algorithms, Performance, Reliability, Theory, Verification