SpringerLink
Log in

A Survey of Exact Arithmetic Implementations

  • Conference paper
  • First Online:
Computability and Complexity in Analysis (CCA 2000)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2064))

Included in the following conference series:

Abstract

This paper provides a survey of practical systems for exact arithmetic. We describe some of the methods used in their implementation, and suggest reasons for the performance differences displayed by some of the competing systems at this years CCA Exact Arithmetic Competition.

Because the practical aspects of the field of exact arithmetic are at an early stage, and many of the systems are prototypes, we have not discussed: portability, user-interfaces, and general usability. It is to be hoped that these aspects might be addressed by participants in any further competitions organised by the CCA committee.

Supported by an EPSRC PhD studentship.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (Canada)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (Canada)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (Canada)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Errett Bishop and Douglas S. Bridges. Constructive Analysis, volume 279 of Grundlehren der mathematischen Wissenschaften. Springer, Berlin, 1985.

    MATH  Google Scholar 

  2. H. Boehm and R. Cartwright. Exact real arithmetic: Formulating real numbers as functions. In D.A. Turner, editor, Research Topics in Functional Programming, University of Texas at Austin Year of Programming, pages 43–64. Addison-Wesley, 1990.

    Google Scholar 

  3. D. Berthelot and M. Daumas. Computing on sequences of embedded intervals. Reliable Computing, 3(3):219–227, 1997.

    Article  MATH  Google Scholar 

  4. J.-C. Bajard, M.D. Ercegovac, L. Imbert, and F. Rico. Fast evaluation of elementary functions with combined shift-and-add polynomial methods. In Fourth Conference on Real Numbers and Computers, pages 75–87, Schloss Dagstuhl, Saarland, Germany, April 2000.

    Google Scholar 

  5. Vasco Brattka and Peter Hertling. Feasible real random access machines. Journal of Complexity, 14(4):490–526, 1998.

    Article  MATH  MathSciNet  Google Scholar 

  6. J. Blanck. Exact real arithmetic systems: results of competion. In Jens Blanck, Vasco Brattka, and Peter Hertling, editors, Computability and Complexity in Analysis 2000, Berlin, 2001. Springer.

    Google Scholar 

  7. R.P. Brent. Fast multiple precision evaluation of elementary functions. Journal of the ACM, 23:242–251, 1976.

    Article  MATH  MathSciNet  Google Scholar 

  8. R.P. Brent. A Fortran multiple precision package. ACM Transactions on Mathematical Software, 4:57–70, 1978.

    Article  Google Scholar 

  9. L. Blum and M. Shub. Evaluating rational functions: Inite precision is finite cost and tractable on average. SIAM Jounal of Computing, 15(2):384–398, 1986.

    Article  MATH  MathSciNet  Google Scholar 

  10. L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society, 21(1), July 1989.

    Google Scholar 

  11. A. Cuyt, P. Kuterna, P.B. Verdonk, and J. Vervloet. The class library for exact rational arithmetic in ARI⊝MOΣ. In Proceedings of the Fourth Real Numbers and Computers, pages 141–160, 2000.

    Google Scholar 

  12. Abbas Edalat and Peter John Potts. A new representation for exact real numbers. Electronical Notes in Theoretical Computer Science, 6:14 pp., 1997. Mathematical foundations of programming semantics (Pittsburgh, PA, 1997).

    MathSciNet  Google Scholar 

  13. C.F. Gauss. Disquisitiones generales circa seriem infinitam \( 1 + \frac{{\alpha \beta }} {{1.\gamma }}x + \frac{{\alpha (\alpha + 1)\beta (\beta + 1)}} {{1.2.\gamma (\gamma + 1)}}xx + \frac{{\alpha (\alpha + 1)(\alpha + 2)\beta (\beta + 1)(\beta + 2)}} {{1.2.3.\gamma (\gamma + 1)(\gamma + 2)}}x^3 \) etc. pars prior. In Werke, volume 3, pages 123–162. Königlichen Gesellschaft der Wissenschaften, Göttingen, 1812.

    MathSciNet  Google Scholar 

  14. P. Gowland and D. Lester. The correctness of an implementation of exact arithmetic. In Proceedings of the Fourth Real Numbers and Computers Conference, pages 125–140, 2000.

    Google Scholar 

  15. R.W. Gosper. Continued fraction arithmetic. HAKMEM 101b, MIT, 1972.

    Google Scholar 

  16. R.W. Gosper. Continued fraction arithmetic. Unpublished Draft Paper, 1977.

    Google Scholar 

  17. Andrzej Grzegorczyk. Computable functionals. FundamentaMathematicae, 42:168–202, 1955.

    MATH  MathSciNet  Google Scholar 

  18. Andrzej Grzegorczyk. On the definitions of computable real continuous functions. Fundamenta Mathematicae, 44:61–71, 1957.

    MATH  MathSciNet  Google Scholar 

  19. Grz59.Andrzej Grzegorczyk. Some approaches to constructive analysis. In A. Heyting, editor, Constructivity in mathematics, Studies in Logic and The Foundations of Mathematics, pages 43–61, Amsterdam, 1959. North-Holland. Colloquium at Amsterdam, 1957.

    Google Scholar 

  20. J. Harrison. Theorem Proving with the Real Numbers. Springer-Verlag, London, 1998.

    MATH  Google Scholar 

  21. T.E. Hull. The use of controlled precision. The Relationship Between Numerical Computation and Programming Languages, pages 71–84, 1982.

    Google Scholar 

  22. A. Hurwitz. Über die Entwicklung Komplexer Grössen in Kettenbrüche. Acta Mathematica, 11:187–200, 1888.

    Article  MathSciNet  Google Scholar 

  23. A. Hurwitz. Über eine besondere Art der Kettenbruch-Entwicklung reeller Grössen. Acta Mathematica, 12:367–405, 1889.

    Article  MathSciNet  Google Scholar 

  24. IEEE, New York. IEEE Standard for Binary Floating-point Arithmetic, IEEE Standard 754-1985, 1985.

    Google Scholar 

  25. IEEE, New York. IEEE Standard for Radix and Format Independent Floating-point Arithmetic, IEEE Standard 854-1994, 1994.

    Google Scholar 

  26. P. Kornerup and D.W. Matula. An on-line arithmetic unit for bit pipelined rational arithmetic. Journal of Parallel and Distributed Computing, 5(3):310–330, 1988.

    Article  Google Scholar 

  27. P. Kornerup and D.W. Matula. An algorithm for redundant binary bit-pipelined rational arithmetic. IEEE Transactions on Computers, 39(8):1106–1115, 1990.

    Article  Google Scholar 

  28. Ko86.Ker-I Ko. On the continued fraction representation of computable real numbers. Theoretical Computer Science, 47:299–313, 1986. corr. ibid., Vol. 54 (1987), Pages 341-343.

    Article  MATH  MathSciNet  Google Scholar 

  29. Ker-I Ko. Complexity Theory of Real Functions. Progress in Theoretical Computer Science. Birkhäuser, Boston, 1991.

    MATH  Google Scholar 

  30. W. Krämer. A priori worst case error bounds for floating-point computations. IEEE Transactions on Computers, 47(7):750–756, 1998.

    Article  Google Scholar 

  31. Daniel Lacombe. Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables r*#x2019;elles I. Comptes Rendus Acadämie des Sciences Paris, 240:2478–2480, June 1955. Thäorie des fonctions.

    MATH  MathSciNet  Google Scholar 

  32. Daniel Lacombe. Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles II. Comptes Rendus Acad_emie des Sciences Paris, 241:13–14, July 1955. Théorie des fonctions.

    MathSciNet  Google Scholar 

  33. Daniel Lacombe. Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles III. Comptes Rendus Académie des Sciences Paris, 241:151–153, July 1955. Théorie des fonctions.

    Google Scholar 

  34. Daniel Lacombe. Sur les possibilites d’extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles. In Le raisonnement en mathematiques et en sciences, pages 67–75, Paris, 1958. Editions du Centre National de la Recherche Scientifique. Colloques Internationaux du Centre National de la Recherche Scientifique, LXX.

    Google Scholar 

  35. V.A. Lee, Jr and H.J. Boehm. Optimizing programs over the constructive reals. In Proceedings of The ACM SIGPLAN’ 90 Conference on Programming Language, Design and Implementation, pages 102–111, 1990.

    Google Scholar 

  36. D. Lester. Effective continued fractions. In Proceedings of the Fifteenth IEEE Arithmetic Conference, June 2001.

    Google Scholar 

  37. Salah Labhalla and Henri Lombardi. Real numbers, continued fractions, and complexity classes. Annals of Pure and Applied Logic, 50:1–28, 1990.

    Article  MATH  MathSciNet  Google Scholar 

  38. A.A. Markov. On the continuity of constructive functions (Russian). Uspekhi Mat. Nauk (N.S.), 9:226–230, 1954.

    MATH  Google Scholar 

  39. MM94.V. Ménissier-Morain. Arithmétique Exacte. PhD thesis, L’Université Paris VII, December 1994.

    Google Scholar 

  40. A. Mostowski. On computable sequences. Fundamenta Mathematicae, 44:37–51, 1957.

    MATH  MathSciNet  Google Scholar 

  41. Norbert Th. Müller. Subpolynomial complexity classes of real functions and real numbers. In Laurent Kott, editor, Proceedings of the 13th International Colloquium on Automata, Languages, and Programming, volume 226 of Lecture Notes in Computer Science, pages 284–293, Berlin, 1986. Springer.

    Google Scholar 

  42. Norbert Th. Müller. Implementing limits in an interactive RealRAM. In J.-M. Chesneaux, F. Jézéquel, J.-L. Lamotte, and J. Vignes, editors, Third Real Numbers and Computers Conference, pages 59–66. Université Pierre et Marie Curie, Paris, 1998. Paris, France, April 27-29, 1998.

    Google Scholar 

  43. J. M. Muller. Some algebraic properties of floating-point arithmetic. In Proceedings of the Fourth Real Numbers and Computers, pages 31–38, 2000

    Google Scholar 

  44. Norbert Th. Müller.The iRRAM: Exact arithmetic in C++. In Jens Blanck, Vasco Brattka, Peter Hertling, and Klaus Weihrauch, editors, Computability and Complexity in Analysis, volume 272 of Informatik Berichte, pages 319–350. FernUniversität Hagen, September 2000. CCA2000 Workshop, Swansea, Wales, September 17-19, 2000.

    Google Scholar 

  45. J. Myhill. What is a real number? The American Mathematical Monthly, 79:748–754, 1972.

    Article  MATH  MathSciNet  Google Scholar 

  46. Marian B. Pour-El and J. Ian Richards. Computability in Analysis and Physics. Perspectives in Mathematical Logic. Springer, Berlin, 1989.

    MATH  Google Scholar 

  47. E.D. Popova. On a formally correct implementation of IEEE computer arithmetic. Journal of Universal Computer Science, 1(7):560–569, 1995.

    MATH  Google Scholar 

  48. P.J. Potts. Exact Real Arithmetic using Möbius Transformations. PhD thesis, Imperial College of Science, Technology and Medicine, London University, March 1999.

    Google Scholar 

  49. H. Rice. Recursive real numbers. Proc. Amer. Math. Soc., 5:784–791, 1954.

    Article  MATH  MathSciNet  Google Scholar 

  50. R.M. Robinson. Review of “Peter, R., Rekursive Funktionen”. The Journal of Symbolic Logic, 16:280–282, 1951.

    Article  Google Scholar 

  51. D.M. Smith. ALGORITHM 693, A FORTRAN package for floating-point multiple-precision arithmetic. ACM Transactions on Mathematical Software, 17(2):273–283, 1991.

    Article  MATH  Google Scholar 

  52. J. Vuillemin. Exact real computer arithmetic with continued fractions. In Proceedings of the 1988 ACM Conference on Lisp and Functional Programming, pages 14-27, Snowbird, Utah, 25–27 July 1988.

    Google Scholar 

  53. Klaus Weihrauch. Computability, volume 9 of EATCS Monographs on Theoretical Computer Science. Springer, Berlin, 1987.

    MATH  Google Scholar 

  54. Klaus Weihrauch. Computable Analysis. Springer, Berlin, 2000.

    MATH  Google Scholar 

  55. Klaus Weihrauch and Christoph Kreitz. Representations of the real numbers and of the open subsets of the set of real numbers. Annals of Pure and Applied Logic, 35:247–260, 1987.

    Article  MATH  MathSciNet  Google Scholar 

  56. P. Zimmermann. MPFR: A library for multiprecision floating-point arithmetic with exact rounding. In Fourth Conference on Real Numbers and Computers, pages 89–90, Schloss Dagstuhl, Saarland, Germany, April 2000.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Manchester University, Oxford Road, Manchester, M13 9PL, UK

    Paul Gowland & David Lester

Authors
  1. Paul Gowland
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David Lester
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. University of Wales Swansea, Singleton Park, Swansea, SA2 8PP, UK

    Jens Blanck

  2. Informatikzentrum, FernUniversität Hagen, 58084, Hagen, Germany

    Vasco Brattka  & Peter Hertling  & 

Rights and permissions

Reprints and permissions

Copyright information

© 2001 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Gowland, P., Lester, D. (2001). A Survey of Exact Arithmetic Implementations. In: Blanck, J., Brattka, V., Hertling, P. (eds) Computability and Complexity in Analysis. CCA 2000. Lecture Notes in Computer Science, vol 2064. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45335-0_3

Download citation

  • DOI: https://doi.org/10.1007/3-540-45335-0_3

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-42197-9

  • Online ISBN: 978-3-540-45335-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation