Arbitrary Precision Arithmetic
Arbitrary Precision
In most computer programs and computing environments, the precision of any calculation (even including addition) is limited by the word size of the computer, that is, by largest number that can be stored in one of the processor's registers. As of mid2002, the most common processor word size is 32 bits, corresponding to the integer . General integer arithmetic on a 32bit machine therefore allows addition of two 32bit numbers to get 33 bits (one word plus an overflow bit), multiplication of two 32bit numbers to get 64 bits (although the most prevalent programming language, C, cannot access the higher word directly and depends on the programmer to either create a machine language function or write a much slower function in C at a final overhead of about nine multiplies more), and division of a 64bit number by a 32bit number creating a 32bit quotient and a 32bit remainder/modulus.
Arbitraryprecision arithmetic consists of a set of algorithms, functions, and data structures designed specifically to deal with numbers that can be of arbitrary size. These functions often modify standard paperandpencil arithmetical techniques (such as long division) and apply them to numbers broken into wordsize chunks.
A major difficulty in creating good arbitraryprecision arithmetic is knowing where to stop a computation. A simple example of this problem is illustrated by the binary expansion of 1/3, which is given by the nonterminating binary decimal . As a result of the fact that exact numbers do not have terminating binary fraction expansions, additional functionality must be built into an arbitrary precision computation system. This can be either in the form of a failsafe, or a configurable 'maximum precision' at which the computation will always stop when it gets to a particular very small number. There are also other ways of going about storing such unfriendlytobinary numbers without losing precisionfor example, one could come up with a data structure that just stores square roots, and then create code to deal with the quirks of such a thing. Mathematica and highend calculators use such a system.
References :
Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Reading, MA: AddisonWesley, 1998.
