arbitrary precision arithmetic

TheInfoList

In computer science, arbitrary-precision arithmetic, also called bignum arithmetic, multiple-precision arithmetic, or sometimes infinite-precision arithmetic, indicates that calculations are performed on numbers whose numerical digit, digits of precision (arithmetic), precision are limited only by the available memory (computers), memory of the host system. This contrasts with the faster fixed-precision arithmetic found in most arithmetic logic unit (ALU) hardware, which typically offers between 8 and 64 bits of precision. Several modern programming languages have built-in support for bignums, and others have libraries available for arbitrary-precision Integer_(computer_science), integer and floating-point math. Rather than store values as a fixed number of bits related to the size of the processor register, these implementations typically use variable-length array data structure, arrays of digits. Arbitrary precision is used in applications where the speed of arithmetic is not a limiting factor, or where Floating point error mitigation, precise results with very large numbers are required. It should not be confused with the symbolic computation provided by many computer algebra systems, which represent numbers by expressions such as , and can thus ''represent'' any computable number with infinite precision.

# Applications

A common application is public-key cryptography, whose algorithms commonly employ arithmetic with integers having hundreds of digits. Another is in situations where artificial limits and arithmetic overflow, overflows would be inappropriate. It is also useful for checking the results of fixed-precision calculations, and for determining optimal or near-optimal values for coefficients needed in formulae, for example the that appears in Gaussian integration. Arbitrary precision arithmetic is also used to compute fundamental mathematical constants such as pi, π to millions or more digits and to analyze the properties of the digit strings A quote example from this article: "Such an extreme pattern is dangerous even if diluted by one of its neighbouring blocks"; this was the occurrence of the sequence 77 twenty-eight times in one block of a thousand digits. or more generally to investigate the precise behaviour of functions such as the Riemann zeta function where certain questions are difficult to explore via analytical methods. 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 arithmetic overflow, overflow, which is an inherent limitation of fixed-precision arithmetic. Similar to a 5-digit odometer's display which changes from 99999 to 00000, a fixed-precision integer may exhibit ''Integer overflow, wraparound'' if numbers grow too large to represent at the fixed level of precision. Some processors can instead deal with overflow by ''saturation arithmetic, saturation,'' which means that if a result would be unrepresentable, it is replaced with the nearest representable value. (With 16-bit unsigned saturation, adding any positive amount to 65535 would yield 65535.) Some processors can generate an exception handling, exception if an arithmetic result exceeds the available precision. Where necessary, the exception can be caught and recovered from—for instance, the operation could be restarted in software using arbitrary-precision arithmetic. In many cases, the task or the programmer can guarantee that the integer values in a specific application will not grow large enough to cause an overflow. Such guarantees may be based on pragmatic limits: a school attendance program may have a task limit of 4,000 students. A programmer may design the computation so that intermediate results stay within specified precision boundaries. Some programming languages such as Lisp (programming language), Lisp, Python (programming language), Python, Perl, Haskell (programming language), Haskell and Ruby (programming language), 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. It also makes it possible to guarantee that arithmetic results will be the same on all machines, regardless of any particular machine's Word (data type), 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 multiple types to represent different levels of precision.

# Implementation issues

Arbitrary-precision arithmetic is considerably slower than arithmetic using numbers that fit entirely within processor registers, since the latter are usually implemented in Arithmetic logic unit, 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. There are exceptions, as certain ''variable word length machine, variable word length'' machines of the 1950s and 1960s, notably the IBM 1620, IBM 1401 and the Honeywell ''Liberator'' series, could manipulate numbers bound only by available storage, with an extra bit that delimited the value. Numbers can be stored in a fixed-point arithmetic, fixed-point format, or in a floating-point format as a significand multiplied by an arbitrary exponent. However, since division almost immediately introduces infinitely repeating sequences of digits (such as 4/7 in decimal, or 1/10 in binary), should this possibility arise then either the representation would be truncated at some satisfactory size or else rational numbers would be used: a large integer for the numerator and for the denominator. But even with the greatest common divisor divided out, arithmetic with rational numbers can become unwieldy very quickly: 1/99 − 1/100 = 1/9900, and if 1/101 is then added, the result is 10001/999900. The size of arbitrary-precision numbers is limited in practice by the total storage available, and computation time. Numerous algorithms have been developed to efficiently perform arithmetic operations on numbers stored with arbitrary precision. In particular, supposing that digits are employed, algorithms have been designed to minimize the asymptotic Computational complexity theory, complexity for large . The simplest algorithms are for addition and subtraction, where one simply adds or subtracts the digits in sequence, carrying as necessary, which yields an algorithm (see big O notation). Comparison (computer programming), Comparison is also very simple. Compare the high-order digits (or machine words) until a difference is found. Comparing the rest of the digits/words is not necessary. The worst case is , but usually it will go much faster. For multiplication, the most straightforward algorithms used for multiplying numbers by hand (as taught in primary school) require operations, but multiplication algorithms that achieve 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 . The Karatsuba algorithm, Karatsuba multiplication is such an algorithm. For Division (mathematics), division, see division algorithm. For a list of algorithms along with complexity estimates, see computational complexity of mathematical operations. For examples in x86 assembly, see #External links, external links.

# Pre-set precision

In some languages such as REXX, the precision of all calculations must be set before doing a calculation. Other languages, such as Python (programming language), Python and Ruby (programming language), Ruby extend the precision automatically to prevent overflow.

# History

IBM's first business computer, the IBM 702 (a vacuum-tube machine) of the mid-1950s, implemented integer arithmetic ''entirely in hardware'' on digit strings of any length from 1 to 511 digits. The earliest widespread software implementation of arbitrary-precision arithmetic was probably that in Maclisp. Later, around 1980, the operating systems VAX/VMS and VM/CMS offered bignum facilities as a collection of literal string, string subprogram, functions in the one case and in the languages EXEC 2 and REXX in the other. An early widespread implementation was available via the IBM 1620 of 1959–1970. The 1620 was a decimal-digit machine which used discrete transistors, yet it had hardware (that used lookup tables) to perform integer arithmetic on digit strings of a length that could be from two to whatever memory was available. For floating-point arithmetic, the mantissa was restricted to a hundred digits or fewer, and the exponent was restricted to two digits only. The largest memory supplied offered 60 000 digits, however Fortran compilers for the 1620 settled on fixed sizes such as 10, though it could be specified on a control card if the default was not satisfactory.

# Software libraries

Arbitrary-precision arithmetic in most computer software is implemented by calling an external library (computer science), library that provides data types and subroutines to store numbers with the requested precision and to perform computations. Different libraries have different ways of representing arbitrary-precision numbers, some libraries work only with integer numbers, others store floating point numbers in a variety of bases (decimal or binary powers). Rather than representing a number as single value, some store numbers as a numerator/denominator pair (rational number, rationals) and some can fully represent computable numbers, though only up to some storage limit. Fundamentally, Turing machines cannot represent all real numbers, as the cardinality of exceeds the cardinality of .

* Karatsuba algorithm * Toom–Cook multiplication * Schönhage–Strassen algorithm * Fürer's algorithm * List of arbitrary-precision arithmetic software * Mixed-precision arithmetic

# References

* , Section 4.3.1: The Classical Algorithms