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 digits of precision are potentially limited only by the available 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 and floating-point math. Rather than storing values as a fixed number of bits related to the size of the processor register, these implementations typically use variable-length arrays of digits.
Arbitrary precision is used in applications where the speed of arithmetic is not a limiting factor, or where 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. recommends important RSA keys be 2048 bits (roughly 600 digits). Another is in situations where artificial limits and 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 π 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 overflow, which is an inherent limitation of fixed-precision arithmetic. Similar to an automobile's odometer display which may change from 99999 to 00000, a fixed-precision integer may exhibit wraparound if numbers grow too large to represent at the fixed level of precision. Some processors can instead 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 any positive amount to 65535 would yield 65535.) Some processors can generate an 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, Python, Perl, Haskell, Ruby and Raku use, or have an option to use, arbitrary-precision numbers for all integer arithmetic. This enables integers to grow to any size limited only by the available memory of the system. Although this reduces performance, it eliminates the concern of incorrect results (or exceptions) due to simple overflow. It also makes it possible to almost 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 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 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. There are exceptions, as certain variable word length machines of the 1950s and 1960s, notably the IBM 1620, IBM 1401 and the Honeywell 200 series, could manipulate numbers bound only by available storage, with an extra bit that delimited the value.
Data structure Numbers can be stored in a 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 in decimal, or 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: , and if is then added, the result is .
The size of arbitrary-precision numbers is limited in practice by the total storage available, and computation time.
Operations 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 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 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 it may complete much faster with operands of similar magnitude.
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 multiplication is such an algorithm.
For 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.
Pre-set precision In some languages such as REXX and ooRexx, the precision of all calculations must be set before doing a calculation. Other languages, such as Python and Ruby, extend the precision automatically to prevent overflow.
Example The calculation of factorials can easily produce very large numbers. This is not a problem for their usage in many formulas (such as Taylor series) because they appear along with other terms, so that—given careful attention to the order of evaluation—intermediate calculation values are not troublesome. If approximate values of factorial numbers are desired, Stirling's approximation gives good results using floating-point arithmetic. The largest representable value for a fixed-size integer variable may be exceeded even for relatively small arguments as shown in the table below. Even floating-point numbers are soon outranged, so it may help to recast the calculations in terms of the logarithm of the number.
But if exact values for large factorials are desired, then special software is required, as in the pseudocode that follows, which implements the classic algorithm to calculate 1, , , ,...: the successive factorial numbers.
constants: Limit = 1000 % Sufficient digits. Base = 10 % The base of the simulated arithmetic. FactorialLimit = 365 % Target number to solve, 365! tdigit: Array[0:9] of character = ["0","1","2","3","4","5","6","7","8","9"]
variables: digit: Array[1:Limit] of 0..9 % The big number. carry, d: Integer % Assistants during multiplication. last: Integer % Index into the big number's digits. text: Array[1:Limit] of character % Scratchpad for the output.
digit[*] := 0 % Clear the whole array. last := 1 % The big number starts as a single-digit, digit := 1 % its only digit is 1.
for n := 1 to FactorialLimit: % Step through producing 1!, 2!, 3!, 4!, etc.
carry := 0 % Start a multiply by n. for i := 1 to last: % Step along every digit. d := digit[i] * n + carry % Multiply a single digit. digit[i] := d mod Base % Keep the low-order digit of the result. carry := d div Base % Carry over to the next digit.
while carry > 0: % Store the remaining carry in the big number. if last >= Limit: error("overflow") last := last + 1 % One more digit. digit[last] := carry mod Base carry := carry div Base % Strip the last digit off the carry.
text[*] := " " % Now prepare the output. for i := 1 to last: % Translate from binary to text. text[Limit - i + 1] := tdigit[digit[i]] % Reversing the order. print text[Limit - last + 1:Limit], " = ", n, "!"
With the example in view, a number of details can be discussed. The most important is the choice of the representation of the big number. In this case, only integer values are required for digits, so an array of fixed-width integers is adequate. It is convenient to have successive elements of the array represent higher powers of the base.
The second most important decision is in the choice of the base of arithmetic, here ten. There are many considerations. The scratchpad variable must be able to hold the result of a single-digit multiply plus the carry from the prior digit's multiply. In base ten, a sixteen-bit integer is certainly adequate as it allows up to 32767. However, this example cheats, in that the value of is not itself limited to a single digit. This has the consequence that the method will fail for or so. In a more general implementation, would also use a multi-digit representation. A second consequence of the shortcut is that after the multi-digit multiply has been completed, the last value of carry may need to be carried into multiple higher-order digits, not just one.
There is also the issue of printing the result in base ten, for human consideration. Because the base is already ten, the result could be shown simply by printing the successive digits of array digit, but they would appear with the highest-order digit last (so that 123 would appear as "321"). The whole array could be printed in reverse order, but that would present the number with leading zeroes ("00000...000123") which may not be appreciated, so this implementation builds the representation in a space-padded text variable and then prints that. The first few results (with spacing every fifth digit and annotation added here) are:
Factorial numbers Reach of computer integers 1 = 1! 2 = 2! 6 = 3! 24 = 4! 120 = 5! 8-bit 255 720 = 6! = 7! = 8! 16-bit = 9! = 10! = 11! = 12! 32-bit = 13! = 14! = 15! = 16! = 17! = 18! = 19! = 20! 64-bit = 21! = 22! = 23! = 24! = 25! = 26! = 27! = 28! = 29! = 30! = 31! = 32! = 33! = 34! 128-bit = 35!