Variable precision

Bibliography of material on Decimal Arithmetic [Index]

Decimal Arithmetic: Variable precision

aber1992
¿Web? Precise Computation Using Range Arithmetic, via C++, Oliver Aberth and Mark J Schaefer, ACM Transactions on Mathematical Software, Vol. 18 #4, pp481–491, ACM Press, December 1992.
Abstract: An arithmetic is described that can replace floating-point arithmetic for programming tasks requiring assured accuracy. A general explanation is given of how the arithmetic is constructed with C++, and a programming example in this language is supplied. Times for solving representative problems are presented.

brent1976
URL
¿Web? Fast multiple-precision evaluation of elementary functions, Richard P. Brent, Journal of the ACM, Vol. 23 #2, pp242–251, ACM Press, April 1976.
Abstract: Let f(x) be one of the usual elementary functions (exp, log, artan, sin, cosh, etc.), and let M(n) be the number of single-precision operations required to multiply n-bit integers. It is shown that f(x) can be evaluated, with relative error O(2^-n), in O(M(n)log(n)) operations, for any floating-point number x (with an n-bit fraction) in a suitable finite interval. From the Schönhage-Strassen bound on M(n), it follows that an n-bit approximation to f(x) may be evaluated in O(n(log(n))²loglog(n)) operations. Special cases include the evaluation of constants such as pi, e, and e^pi. The algorithms depend on the theory of elliptic integrals, using the arithmetic-geometric

brent1981
URL
¿Web? MP User's Guide (Fourth Edition), Richard P. Brent, 73pp, Dept. Computer Science, Australian National University, Canberra, TR-CS-81-08, June 1981.
Abstract: MP is a multiple-precision floating-point arithmetic package. It is almost completely machine-independent, and should run on any machine with an ANSI Standard Fortran (ANS X3.9-1966) compiler, sufficient memory, and a wordlength (for integer arithmetic) of at least 16 bits. A precompiler (Augment) which facilitates the use of the MP package is available. ...
    MP works with normalized floating-point numbers. The base (B) and number of digits (T) are arbitrary, subject to some restrictions given below, and may be varied dynamically. ...

chart1966
¿Web? Automatic Controlled Precision Calculations, Bruce A. Chartres, Journal of the ACM, Vol. 13 #3, pp386–403, ACM Press, July 1966.
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.

cohen1983
¿Web? CADAC: A Controlled-Precision Decimal Arithmetic Unit, Marty S. Cohen, T. E. Hull, and V. Carl Hamacher, IEEE Transactions on Computers, Vol. 32 #4, pp370–377, IEEE, April 1983.
Abstract: This paper describes the design of an arithmetic unit called CADAC (clean arithmetic with decimal base and controlled precision). Programming language specifications for carrying out “ideal” floating-point arithmetic are described first. These specifications include detailed requirements for dynamic precision control and exception handling, along with both complex and interval arithmetic at the level of a programming language such as Fortran or PL/I.
    CADAC is an arithmetic unit which performs the four floating-point operations add/subtract/multiply/divide on decimal numbers in such a way as to support all the language requirements efficiently. A three-level pipeline is used to overlap two-digit-at-a-time serial processing of the partial products/remainders. Although the logic design is relatively complex, the performance is efficient, and the advantages gained by implementing programmer-controlled precision directly in the hardware are significant.

cowlis1984
¿Web? The Design of the REXX Language, M. F. Cowlishaw, IBM Systems Journal, Vol. 23 #4, pp326–335, IBM (Offprint # G321-5228), 1984.
Abstract: One way of classifying computer languages is by two classes: languages needing skilled programmers, and personal languages used by an expanding population of general users. REstructured eXtended eXecutor (REXX) is a flexible personal language designed with particular attention to feedback from its users. It has proved to be effective and easy to use, yet it is sufficiently general and powerful to fulfill the needs of many demanding professional applications. REXX is system and hardware independent, so that it has been possible to integrate it experimentally into several operating systems. Here REXX is used for such purposes as command and macro programming, prototyping, education, and personal programming. This study introduces REXX and describes the basic design principles that were followed in developing it.
Note: First published as IBM Hursley Technical Report TR12.223, October 1983.

cowlis2003
URL
¿Web? Decimal Floating-Point: Algorism for Computers, Michael F. Cowlishaw, Proceedings of the 16th IEEE Symposium on Computer Arithmetic, ISBN 0-7695-1894-X, pp104–111, IEEE, June 2003.
Abstract: Decimal arithmetic is the norm in human calculations, and human-centric applications must use a decimal floating-point arithmetic to achieve the same results.
    Initial benchmarks indicate that some applications spend 50% to 90% of their time in decimal processing, because software decimal arithmetic suffers a 100× to 1000× performance penalty over hardware. The need for decimal floating-point in hardware is urgent.
    Existing designs, however, either fail to conform to modern standards or are incompatible with the established rules of decimal arithmetic. This paper introduces a new approach to decimal floating-point which not only provides the strict results which are necessary for commercial applications but also meets the constraints and requirements of the IEEE 854 standard.
    A hardware implementation of this arithmetic is in development, and it is expected that this will significantly accelerate a wide variety of applications.
Note: Softcopy is available in PDF.

cowlis2004
¿Web? Fixed, floating, and exact computation with Java's BigDecimal, M. Cowlishaw, J. Bloch, and J.D. Darcy, Dr. Dobb's Journal Vol. 29 #7, ISSN 1044-789X, pp22–27, CMP Media, July 2004.
Abstract: Decimal data types are widely used in commercial, financial, and Web applications, and many general-purpose programming languages have either native decimal types or readily available decimal arithmetic packages. Since the 1.1 release, the libraries of the Java programming language supported decimal arithmetic via the Java.math.BigDecimal class. With the inclusion of JSR13 into J2SE 1.5, BigDecimal now has true floating-point operations consistent with those in the IEEE 754 revision. In this article, we first explain why decimal arithmetic is important and the differences between the BigDecimal class and binary float and double types.

golds1946
¿Web? The Electronic Numerical Integrator and Computer (ENIAC), H. H. Goldstine and Adele Goldstine, IEEE Annals of the History of Computing, Vol. 18 #1, pp10–16, IEEE, 1996.
Abstract: It is our purpose in the succeeding pages to give a brief description of the ENIAC and an indication of the kinds of problems for which it can be used. This general purpose electronic computing machine was recently made public by the Army Ordnance Department for which it was developed by the Moore School of Electrical Engineering. The machine was developed primarily for the purpose of calculating firing tablcs for the armed forces. Its design is, however, sufficiently general to permit the solution of a large class of numerical problems which could hardly be attempted by more conventional computing tools.
    In order easily to obtain sufficient accuracy for scientific computations, the ENIAC was designed as a digital device. The equipment normally handles signed 10-digit numbers expressed in the decimal system. It is, however, so constructed that operations with as many as 20 digits are possible.
    The machine is automatically sequenced in the sense that all instructions needed to carry out a computation are given to it before the computation commences. It will be seen below how these instructions are given to the machine.
Note: Reprinted from Mathematical Tables and Other Aids to Computation, 1946.

hull1978
¿Web? Desirable Floating-Point Arithmetic and Elementary Functions for Numerical Computation, T. E. Hull, ACM Signum Newsletter, Vol. 14 #1 (Proceedings of the SIGNUM Conference on the Programming Environment for Development of Numerical Software), pp96–99, ACM Press, 1978.
Abstract: The purpose of this talk is to summarize proposed specifications for floating-point arithmetic and elementary functions. The topics considered are: the base of the number system, precision control, number representation, arithmetic operations, other basic operations, elementary functions, and exception handling. The possibility of doing without fixed-point arithmetic is also mentioned. The specifications are intended to be entirely at the level of a programming language such as Fortran. The emphasis is on convenience and simplicity from the user’s point of view. Conforming to such specifications would have obvious beneficial implications for the portability of numerical software, and for proving programs correct, as well as attempting to provide facilities which are most suitable for the user. The specifications are not complete in every detail, but it is intended that they be complete “in spirit” – some further details, especially syntactic details, would have to be provided, but the proposals are otherwise relatively complete.
Note: Also in Proceedings of the IEEE 4th Symposium on Computer Arithmetic pp63-69.

hull1985b
¿Web? Properly Rounded Variable Precision Square Root, T. E. Hull and A. Abrham, ACM Transactions on Mathematical Software, Vol. 11 #3, pp229–237, ACM Press, September 1985.
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 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.

hull1986
¿Web? Variable Precision Exponential Function, T. E. Hull and A. Abrham, ACM Transactions on Mathematical Software, Vol. 12 #2, pp79–91, ACM Press, June 1986.
Abstract: The exponential function presented here returns a result which differs from e^x by less than one unit in the last place, for any representable value of x which is not too close to values for which e^x would overflow or underflow. (For values of x which are not within this range, an error condition is raised.) It is a “variable precision” function in that it returns a p-digit approximation for a p-digit argument, for any p > 0 (p-digit means p-decimal-digit). The program and analysis are valid for all p > 0, but current implementations place a restriction on p. The program is presented in a Pascal-like programming language called Numerical Turing which has special facilities for scientific computing, including precision control, directed roundings, and built-in functions for getting and setting exponents.

hull1991
¿Web? Specifications for a Variable-Precision Arithmetic Coprocessor, T. E. Hull, M. S. Cohen, and C. B. Hall, Proceedings. 10th Symposium on Computer Arithmetic, ISBN 0-8186-9151-4, pp127–131, IEEE, 1991.
Abstract: The authors have been developing a programming system intended to be especially convenient for scientific computing. Its main features are variable precision (decimal) floating-point arithmetic and convenient exception handling. The software implementation of the system has evolved over a number of years, and a partial hardware implementation of the arithmetic itself was constructed and used during the early stages of the project. Based on this experience, the authors have developed a set of specifications for an arithmetic coprocessor to support such a system. The main purpose of this paper is to describe these specifications. An outline of the language features and how they can be used is also provided, to help justify our particular choice of coprocessor specifications.

kahn2004
¿Web? The child-engineering of arithmetic in ToonTalk, Ken Kahn, Proceedings of the 2004 conference on Interaction Design and Children, ISBN 1-58113-791-5, pp141–142, ACM Press, 2004.
Abstract: Providing a child-appropriate interface to an arithmetic package with large numbers and exact fractions is surprisingly challenging. We discuss solutions to problems ranging from how to present fractions such as 1/3 to how to deal with numbers with tens of thousands of digits. As with other objects in ToonTalk�, we strive to make the enhanced numbers work in a concrete and playful manner.

knuth1998
URL
¿Web? The Art of Computer Programming, Vol 2, Donald E. Knuth, ISBN 0-201-89684-2, 762pp, Addison Wesley Longman, 1998.
Abstract: The chief purpose of this chapter [4] is to make a careful study of the four basic processes of arithmetic: addition, subtraction, multiplication, and division. Many people see arithmetic as a trivial thing that children learn and computers do, but we will see that arithmetic is a fascinating topic with many interesting facets. ...
Note: Third edition. See especially sections 4.1 through 4.4.

smith2003
URL
¿Web? Using multiple-precision arithmetic, David M Smith, Computing in Science and Engineering, Vol. 5 #4, pp88–93, IEEE Computer Society, July 2003.
Abstract: High-precision arithmetic is useful in many different computational problems. The most common is a numerically unstable algorithm, for which, say, 53-bit (ANSI/IEEE 754-1985 Standard) double precision would not yield a sufficiently accurate result.
Note: Related papers by same author at: http://myweb.lmu.edu/dmsmith/FMLIB.html

The 16 references listed on this page are selected from the bibliography on Decimal Arithmetic collected by Mike Cowlishaw. Please see the index page for more details and other categories.

aber1992 ¿Web?	Precise Computation Using Range Arithmetic, via C++, Oliver Aberth and Mark J Schaefer, ACM Transactions on Mathematical Software, Vol. 18 #4, pp481–491, ACM Press, December 1992. Abstract: An arithmetic is described that can replace floating-point arithmetic for programming tasks requiring assured accuracy. A general explanation is given of how the arithmetic is constructed with C++, and a programming example in this language is supplied. Times for solving representative problems are presented.
brent1976 URL ¿Web?	Fast multiple-precision evaluation of elementary functions, Richard P. Brent, Journal of the ACM, Vol. 23 #2, pp242–251, ACM Press, April 1976. Abstract: Let f(x) be one of the usual elementary functions (exp, log, artan, sin, cosh, etc.), and let M(n) be the number of single-precision operations required to multiply n-bit integers. It is shown that f(x) can be evaluated, with relative error O(2^-n), in O(M(n)log(n)) operations, for any floating-point number x (with an n-bit fraction) in a suitable finite interval. From the Schönhage-Strassen bound on M(n), it follows that an n-bit approximation to f(x) may be evaluated in O(n(log(n))²loglog(n)) operations. Special cases include the evaluation of constants such as pi, e, and e^pi. The algorithms depend on the theory of elliptic integrals, using the arithmetic-geometric
brent1981 URL ¿Web?	MP User's Guide (Fourth Edition), Richard P. Brent, 73pp, Dept. Computer Science, Australian National University, Canberra, TR-CS-81-08, June 1981. Abstract: MP is a multiple-precision floating-point arithmetic package. It is almost completely machine-independent, and should run on any machine with an ANSI Standard Fortran (ANS X3.9-1966) compiler, sufficient memory, and a wordlength (for integer arithmetic) of at least 16 bits. A precompiler (Augment) which facilitates the use of the MP package is available. ... MP works with normalized floating-point numbers. The base (B) and number of digits (T) are arbitrary, subject to some restrictions given below, and may be varied dynamically. ...
chart1966 ¿Web?	Automatic Controlled Precision Calculations, Bruce A. Chartres, Journal of the ACM, Vol. 13 #3, pp386–403, ACM Press, July 1966. 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.
cohen1983 ¿Web?	CADAC: A Controlled-Precision Decimal Arithmetic Unit, Marty S. Cohen, T. E. Hull, and V. Carl Hamacher, IEEE Transactions on Computers, Vol. 32 #4, pp370–377, IEEE, April 1983. Abstract: This paper describes the design of an arithmetic unit called CADAC (clean arithmetic with decimal base and controlled precision). Programming language specifications for carrying out “ideal” floating-point arithmetic are described first. These specifications include detailed requirements for dynamic precision control and exception handling, along with both complex and interval arithmetic at the level of a programming language such as Fortran or PL/I. CADAC is an arithmetic unit which performs the four floating-point operations add/subtract/multiply/divide on decimal numbers in such a way as to support all the language requirements efficiently. A three-level pipeline is used to overlap two-digit-at-a-time serial processing of the partial products/remainders. Although the logic design is relatively complex, the performance is efficient, and the advantages gained by implementing programmer-controlled precision directly in the hardware are significant.
cowlis1984 ¿Web?	The Design of the REXX Language, M. F. Cowlishaw, IBM Systems Journal, Vol. 23 #4, pp326–335, IBM (Offprint # G321-5228), 1984. Abstract: One way of classifying computer languages is by two classes: languages needing skilled programmers, and personal languages used by an expanding population of general users. REstructured eXtended eXecutor (REXX) is a flexible personal language designed with particular attention to feedback from its users. It has proved to be effective and easy to use, yet it is sufficiently general and powerful to fulfill the needs of many demanding professional applications. REXX is system and hardware independent, so that it has been possible to integrate it experimentally into several operating systems. Here REXX is used for such purposes as command and macro programming, prototyping, education, and personal programming. This study introduces REXX and describes the basic design principles that were followed in developing it. Note: First published as IBM Hursley Technical Report TR12.223, October 1983.
cowlis2003 URL ¿Web?	Decimal Floating-Point: Algorism for Computers, Michael F. Cowlishaw, Proceedings of the 16th IEEE Symposium on Computer Arithmetic, ISBN 0-7695-1894-X, pp104–111, IEEE, June 2003. Abstract: Decimal arithmetic is the norm in human calculations, and human-centric applications must use a decimal floating-point arithmetic to achieve the same results. Initial benchmarks indicate that some applications spend 50% to 90% of their time in decimal processing, because software decimal arithmetic suffers a 100× to 1000× performance penalty over hardware. The need for decimal floating-point in hardware is urgent. Existing designs, however, either fail to conform to modern standards or are incompatible with the established rules of decimal arithmetic. This paper introduces a new approach to decimal floating-point which not only provides the strict results which are necessary for commercial applications but also meets the constraints and requirements of the IEEE 854 standard. A hardware implementation of this arithmetic is in development, and it is expected that this will significantly accelerate a wide variety of applications. Note: Softcopy is available in PDF.
cowlis2004 ¿Web?	Fixed, floating, and exact computation with Java's BigDecimal, M. Cowlishaw, J. Bloch, and J.D. Darcy, Dr. Dobb's Journal Vol. 29 #7, ISSN 1044-789X, pp22–27, CMP Media, July 2004. Abstract: Decimal data types are widely used in commercial, financial, and Web applications, and many general-purpose programming languages have either native decimal types or readily available decimal arithmetic packages. Since the 1.1 release, the libraries of the Java programming language supported decimal arithmetic via the Java.math.BigDecimal class. With the inclusion of JSR13 into J2SE 1.5, BigDecimal now has true floating-point operations consistent with those in the IEEE 754 revision. In this article, we first explain why decimal arithmetic is important and the differences between the BigDecimal class and binary float and double types.
golds1946 ¿Web?	The Electronic Numerical Integrator and Computer (ENIAC), H. H. Goldstine and Adele Goldstine, IEEE Annals of the History of Computing, Vol. 18 #1, pp10–16, IEEE, 1996. Abstract: It is our purpose in the succeeding pages to give a brief description of the ENIAC and an indication of the kinds of problems for which it can be used. This general purpose electronic computing machine was recently made public by the Army Ordnance Department for which it was developed by the Moore School of Electrical Engineering. The machine was developed primarily for the purpose of calculating firing tablcs for the armed forces. Its design is, however, sufficiently general to permit the solution of a large class of numerical problems which could hardly be attempted by more conventional computing tools. In order easily to obtain sufficient accuracy for scientific computations, the ENIAC was designed as a digital device. The equipment normally handles signed 10-digit numbers expressed in the decimal system. It is, however, so constructed that operations with as many as 20 digits are possible. The machine is automatically sequenced in the sense that all instructions needed to carry out a computation are given to it before the computation commences. It will be seen below how these instructions are given to the machine. Note: Reprinted from Mathematical Tables and Other Aids to Computation, 1946.
hull1978 ¿Web?	Desirable Floating-Point Arithmetic and Elementary Functions for Numerical Computation, T. E. Hull, ACM Signum Newsletter, Vol. 14 #1 (Proceedings of the SIGNUM Conference on the Programming Environment for Development of Numerical Software), pp96–99, ACM Press, 1978. Abstract: The purpose of this talk is to summarize proposed specifications for floating-point arithmetic and elementary functions. The topics considered are: the base of the number system, precision control, number representation, arithmetic operations, other basic operations, elementary functions, and exception handling. The possibility of doing without fixed-point arithmetic is also mentioned. The specifications are intended to be entirely at the level of a programming language such as Fortran. The emphasis is on convenience and simplicity from the user’s point of view. Conforming to such specifications would have obvious beneficial implications for the portability of numerical software, and for proving programs correct, as well as attempting to provide facilities which are most suitable for the user. The specifications are not complete in every detail, but it is intended that they be complete “in spirit” – some further details, especially syntactic details, would have to be provided, but the proposals are otherwise relatively complete. Note: Also in Proceedings of the IEEE 4th Symposium on Computer Arithmetic pp63-69.
hull1985b ¿Web?	Properly Rounded Variable Precision Square Root, T. E. Hull and A. Abrham, ACM Transactions on Mathematical Software, Vol. 11 #3, pp229–237, ACM Press, September 1985. 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 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.
hull1986 ¿Web?	Variable Precision Exponential Function, T. E. Hull and A. Abrham, ACM Transactions on Mathematical Software, Vol. 12 #2, pp79–91, ACM Press, June 1986. Abstract: The exponential function presented here returns a result which differs from e^x by less than one unit in the last place, for any representable value of x which is not too close to values for which e^x would overflow or underflow. (For values of x which are not within this range, an error condition is raised.) It is a “variable precision” function in that it returns a p-digit approximation for a p-digit argument, for any p > 0 (p-digit means p-decimal-digit). The program and analysis are valid for all p > 0, but current implementations place a restriction on p. The program is presented in a Pascal-like programming language called Numerical Turing which has special facilities for scientific computing, including precision control, directed roundings, and built-in functions for getting and setting exponents.
hull1991 ¿Web?	Specifications for a Variable-Precision Arithmetic Coprocessor, T. E. Hull, M. S. Cohen, and C. B. Hall, Proceedings. 10th Symposium on Computer Arithmetic, ISBN 0-8186-9151-4, pp127–131, IEEE, 1991. Abstract: The authors have been developing a programming system intended to be especially convenient for scientific computing. Its main features are variable precision (decimal) floating-point arithmetic and convenient exception handling. The software implementation of the system has evolved over a number of years, and a partial hardware implementation of the arithmetic itself was constructed and used during the early stages of the project. Based on this experience, the authors have developed a set of specifications for an arithmetic coprocessor to support such a system. The main purpose of this paper is to describe these specifications. An outline of the language features and how they can be used is also provided, to help justify our particular choice of coprocessor specifications.
kahn2004 ¿Web?	The child-engineering of arithmetic in ToonTalk, Ken Kahn, Proceedings of the 2004 conference on Interaction Design and Children, ISBN 1-58113-791-5, pp141–142, ACM Press, 2004. Abstract: Providing a child-appropriate interface to an arithmetic package with large numbers and exact fractions is surprisingly challenging. We discuss solutions to problems ranging from how to present fractions such as 1/3 to how to deal with numbers with tens of thousands of digits. As with other objects in ToonTalk�, we strive to make the enhanced numbers work in a concrete and playful manner.
knuth1998 URL ¿Web?	The Art of Computer Programming, Vol 2, Donald E. Knuth, ISBN 0-201-89684-2, 762pp, Addison Wesley Longman, 1998. Abstract: The chief purpose of this chapter [4] is to make a careful study of the four basic processes of arithmetic: addition, subtraction, multiplication, and division. Many people see arithmetic as a trivial thing that children learn and computers do, but we will see that arithmetic is a fascinating topic with many interesting facets. ... Note: Third edition. See especially sections 4.1 through 4.4.
smith2003 URL ¿Web?	Using multiple-precision arithmetic, David M Smith, Computing in Science and Engineering, Vol. 5 #4, pp88–93, IEEE Computer Society, July 2003. Abstract: High-precision arithmetic is useful in many different computational problems. The most common is a numerically unstable algorithm, for which, say, 53-bit (ANSI/IEEE 754-1985 Standard) double precision would not yield a sufficiently accurate result. Note: Related papers by same author at: http://myweb.lmu.edu/dmsmith/FMLIB.html