Arbitrary-precision arithmetic

From Wikipedia, the free encyclopedia

You have new messages (last change).
Some information in this article or section is not attributed to sources and may not be reliable.
Please check for inaccuracies, and modify and cite sources as needed.

On a computer, arbitrary-precision arithmetic, also called bignum arithmetic, is a technique that allows computer programs to perform calculations on integers or rational numbers (including floating-point numbers) with an arbitrary number of digits of precision, typically limited only by the available memory of the host system. It is often implemented by storing a number as a variable-length array of digits in some base, in contrast to most computer arithmetic which uses a fixed number of bits related to the size of the processor registers. Rational numbers can be stored as a pair of two integers for the numerator and denominator, in a fixed-point format with a fixed denominator, or in a floating-point format as a significand multiplied by an arbitrary exponent.

The earliest widespread implementation of arbitrary precision arithmetic was probably that in Maclisp. Later, around 1980, the VAX/VMS and VM/CMS operating systems offered bignum facilities as a collection of string functions in the one case and in the EXEC 2 and REXX languages in the other. Today, arbitrary-precision libraries are available for most modern programming languages (see below). Almost all computer algebra systems implement arbitrary-precision arithmetic.

Arbitrary-precision arithmetic is sometimes called infinite-precision arithmetic, which is something of a misnomer: the number of digits of precision always remains finite (and is bounded in practice), although it can grow very large.

Arbitrary-precision arithmetic should not be confused with symbolic computation, as provided by computer algebra systems. The latter represent numbers by symbolic expressions such as πsin(3), or even by computer programs, and in this way can symbolically represent any computable number (limited by available memory). Numeric results can still only be provided to arbitrary (finite) precision in general, however, by evaluating the symbolic expression using arbitrary-precision arithmetic.

Contents

[edit] Applications

Arbitrary-precision arithmetic is usually slower than arithmetic using numbers that fit entirely within processor registers, since the latter are usually implemented in hardware arithmetic whereas the former must be implemented in software. Consequently, arbitrary precision is used in applications where arithmetic performance is not a limiting factor, or where precise results or exact integer arithmetic with very large numbers is required. It is also useful for checking the results of fixed-precision calculations.

A common application is public-key cryptography, whose algorithms commonly employ arithmetic with integers of hundreds or thousands of digits; another is in human-centric applications where artificial limits and overflows would be inappropriate.

Arbitrary precision arithmetic is also used to compute fundamental mathematical constants such as pi to millions or more digits and to analyze their properties. Another example is in rendering Fractal images with an extremely high magnification, such as those found in the Mandelbrot set.

Arbitrary-precision arithmetic can also be used to avoid overflow, which is an inherent limitation of fixed-precision arithmetic. Just like a 4-digit odometer which rolls around from 9999 to 0000, a fixed-precision integer can exhibit wraparound if numbers grow too large to represent at the fixed level of precision. Some processors can deal with overflow by saturation, which means that if a result would be unrepresentable, it is replaced with the nearest representable value. (With 16-bit unsigned saturation, adding 1 to 65535 yields 65535 — see saturation arithmetic.) Some processors can generate an exception if an arithmetic result exceeds the available precision. Where necessary, the exception can be caught and the operation can be restarted in software with arbitrary-precision operands.

Since many computers now routinely use 32-bit or even 64-bit integers, it can often be guaranteed that the integer numbers in a specific application will never grow large enough to cause an overflow. However, some programming languages such as Scheme, Lisp, Rexx, Python, Perl and Ruby use, or have an option to use, arbitrary-precision numbers for all arithmetic. Although this reduces performance, it eliminates the possibility of incorrect results (or exceptions) due to overflow, and makes it possible to guarantee that arithmetic results will be the same on all machines, regardless of any particular machine’s word size. The exclusive use of arbitrary-precision numbers in a programming language also simplifies the language, because “a number is a number” and there is no need for the multiplicity of types needed to represent different levels of precision.

[edit] Algorithms

Numerous algorithms have been developed to efficiently perform arithmetic operations on numbers stored with arbitrary precision. In particular, supposing that N digits are employed, algorithms have been designed to minimize the asymptotic complexity for large N.

The simplest algorithms are for addition and subtraction, where one simply adds or subtracts the digits in sequence, carrying as necessary, which yields an O(N) algorithm (see big O notation).

For multiplication, the most straightforward algorithms used for multiplying numbers by hand requires O(N2) operations, but multiplication algorithms that achieve O(Nlog(N)log(log(N))) complexity have been devised based on fast Fourier transforms, and there are also algorithms with slightly worse complexity but with sometimes superior real-world performance for smaller N.

For a list of algorithms along with complexity estimates, see: Computational complexity of mathematical operations

[edit] Arbitrary-precision software

Arbitrary-precision arithmetic in most computer software is implemented by calling an external library that provides datatypes and subroutines to store numbers with the requested precision and to perform computations.


Stand-alone application software that supports arbitrary precision computations:

[edit] References

    • Knuth, Donald, The Art of Computer Programming, ISBN 0-201-89684-2, Volume 2: Seminumerical Algorithms, Section 4.3.1: The Classical Algorithms
    Retrieved from "http://en.wikipedia.org../../../a/r/b/Arbitrary-precision_arithmetic.html"
    In other languages