Constructive real interpretation of numerical programs

ABSTRACT

We explore the feasibility of providing exact real arithmetic for use in conventional numerical programs. We have built a prototype interpreter which replaces floating point operations with operations on constructive real numbers in the execution of conventional Fortran programs. Such a facility makes it unnecessary to concern oneself with issues of numerical stability in the solution of small problems. It also provides a useful tool for the development of larger numerical programs.We discuss the computability and algorithmic issues involved in the design of the interpreter, as well as some preliminary experiences and performance measurements.

REFERENCES

• 1: J. A. Abbott , R. J. Bradford , J. H. Davenport, The Bath algebraic number package, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.250-253, July 21-23, 1986, Waterloo, Ontario, Canada [doi>10.1145/32439.32490]
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: [Bis 67] Bishop, Errett, Foundations of Constructive Analysis, McGraw-Hill, New York, 1967.
• 4: [Bri 79] Bridges, D. S., Constructive Functional Analysis, Pitman, London, 1979.
• 5: [Boe 85] Boehm, Hans-J., Alan Demers, and James Donahue, "A Programmer's Introduction to Russell", Technical Report 85-16, Department of Computer Science, Rice University.
• 6: Hans-Juergen Boehm , Alan Demers, Implementing RUSSELL, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.186-195, June 25-27, 1986, Palo Alto, California, United States
• 7: Hans-J. Boehm , Robert Cartwright , Mark Riggle , Michael J. O'Donnell, Exact real arithmetic: a case study in higher order programming, Proceedings of the 1986 ACM conference on LISP and functional programming, p.162-173, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319860]
• 8: [Cart 82] Cartwright, Robert S., et al., "Rn: An Experimental Computer Network to Support Numerical Computation", Technical Report, Mathematical Sciences Department, Rice University, 1982.
• 9: [Cha 87] Chase, Benjamin B., and Robert T. Hood, "Selective Interpretation as a Technique for Debugging Computationally Intensive Programs", Proceedings, SIGPLAN '87 Symposium.
• 10: James Donahue , Alan Demers, Data types are values, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.426-445, July 1985 [doi>10.1145/3916.3987]
• 11: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 12: Ramon E. Moore , Fritz Bierbaum, Methods and Applications of Interval Analysis (SIAM Studies in Applied and Numerical Mathematics) (Siam Studies in Applied Mathematics, 2.), Soc for Industrial & Applied Math, 1979
• 13: [Myh 72] Myhill, J., "What is a Real Number?", American Mathematical Monthly 79, 7 (1972), pp. 748-754.
• 14: Michael J. O'Donnell, Equational logic as a programming language, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 15: [Ort 72] Ortega, James M., Numerical Analysis: A Second Course, Academic Press, 1972, pp. 189-193.
• 16: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
• 17: [Wie 80] Wiedmer, E., "Computing with Infinite Objects", Theoretical Computer Science 10 (1980), pp. 133-155.

INDEX TERMS

Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Interpreters

  G. Mathematics of Computing

General Terms:
Algorithms, Design, Languages, Theory