Arbitrary-precision arithmetic

From Free net encyclopedia

On a computer, arbitrary-precision arithmetic, also called bignum arithmetic, is a technique that allows computer programs to perform calculations on integers and rational numbers with an arbitrary number of digits of precision, limited only by the available memory of the host system. It typically works 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 given by 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.

Perhaps the earliest widespread implementation of arbitrary precision arithmetic was in Maclisp. Later, the VAX/VMS operating system offered bignum facilities as a collection of string functions. Today, bignum libraries are available for most modern programming languages (see below). Almost all computer algebra systems implement arbitrary precision arithmetic.

[edit]

Applications

Arbitrary-precision arithmetic is usually much 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 only used in a limited range of applications that require extremely precise results or exact integer arithmetic with very large numbers.

The most common application is encryption, whose algorithms commonly employ arithmetic with integers of hundreds or thousands of digits.

Arbitrary precision arithmetic is also used to compute fundamental mathematical constants such as pi to millions or more digits and to analyze their properties.


[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 algorithm is for addition, where one simply adds 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 <math>O(N^2)</math> operations, but <math>O(N \log(N) \log(\log(N)))</math> multiplication algorithms have been devised (and also algorithms with slightly worse complexity but with sometimes superior real-world performance for moderate N).


[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.

Retrieved from "http://www.netipedia.com/index.php/Arbitrary-precision_arithmetic"