Arbitrary-precision arithmetic
From Wikipedia, the free encyclopedia
Categories: Articles needing additional references from July 2007 | Computer arithmetic | Arbitrary precision algorithms
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. Using many digits of precision, as opposed to the 8–16 digits available in most hardware arithmetic, is important for a number of applications as described below; the most widespread usage is probably for cryptography (used, e.g., in every modern web browser). 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. An early widespread implementation was available via the IBM 1620 of 1959-1970 which was a decimal-digit machine that despite using discrete transistors had hardware that performed integer or floating-point arithmetic (via lookup tables) on digit strings of a length that could be from two to whatever memory was available, though the mantissa of floating-point numbers was restricted to 100 digits or less and the exponent of floating-point numbers was restricted to two digits only: the largest memory supplied offered sixty thousands digits. Compilers for the IBM 1620 (Fortran), however, settled on some fixed size (which could be specified on a control card if the default was not satisfactory), such as ten digits. IBM's first business computer, the IBM 702, which was a vacuum tube machine, implemented integer arithmetic entirely in hardware on digit strings of any length from one to 511 digits. The earliest widespread software 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. Aside from the question of the total storage available, the variables used by the software to index the digit strings are themselves limited in size. 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 Failed to parse (Missing texvc executable; please see math/README to configure.): \pi \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.
ApplicationsArbitrary-precision arithmetic is considerably 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. Even if the computer lacks hardware for certain operations (such as integer division, or all floating-point operations) and software is provided instead it will use number sizes closely related to the available hardware registers: one or two words only and definitely not N words. Consequently, arbitrary precision is used in applications where the speed of arithmetic 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, and for determining the best possible value for coefficients needed in formulae, such as the Failed to parse (Missing texvc executable; please see math/README to configure.): \sqrt{1/3} that appears in Gaussian integration. 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 π to millions or more digits and to analyze the properties of the digit strings, or more generally to investigate the precise behaviour of functions such as the Riemann Zeta function where answers via analytical methods are difficult to obtain. 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, though as time passes the exact nature of the constraint can be forgotten, as in implementations of the Binary search method which often employ the form (L + R)/2; this means that for correct functioning the sum of L and R is limited to sixteen bits (or thirty-two, etc.), not the individual variables. 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 integer arithmetic. Although this reduces performance, it eliminates the possibility of incorrect results (or exceptions) due to simple 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. AlgorithmsNumerous 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 (as taught in primary school) requires Failed to parse (Missing texvc executable; please see math/README to configure.): O(N^2) operations, but multiplication algorithms that achieve Failed to parse (Missing texvc executable; please see math/README to configure.): O(N \log(N) \log(\log(N))) complexity have been devised, such as the Schönhage-Strassen algorithm, 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 Arbitrary-precision softwareArbitrary-precision arithmetic in most computer software is implemented by calling an external library that provides data types and subroutines to store numbers with the requested precision and to perform computations.
Stand-alone application software that supports arbitrary precision computations:
References
fr:Arithmétique multiprécision ja:多倍長整数 pl:Duże liczby całkowite pt:Bignum sv:Bignum-aritmetik |
