Arbitrary-precision arithmetic

Last updated

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

Contents

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 store 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 π·sin(2), 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. [1] [2] 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. [3]

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 [4] 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 a 5-digit odometer's display which changes 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 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. It also 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 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 and definitely not N words. There are exceptions, as certain 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 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 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).

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 ${\displaystyle \Theta }$(N), 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 ${\displaystyle \Theta }$(N2) operations, but multiplication algorithms that achieve 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. 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, 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, 1×2, 1×2×3, 1×2×3×4, etc. the successive factorial numbers.

`Constant Limit = 1000;            % Sufficient digits. Constant Base = 10;               % The base of the simulated arithmetic. Constant FactorialLimit = 365;    % Target number to solve, 365! Array digit[1:Limit] of integer;  % The big number. Integer carry,d;                  % Assistants during multiplication. Integer last,i;                   % Indices to the big number's digits. Array text[1:Limit] of character; % Scratchpad for the output. Constant tdigit[0:9] of character = ["0","1","2","3","4","5","6","7","8","9"]; BEGIN  digit:=0;                        % Clear the whole array.  digit[1]:=1;                     % The big number starts with 1,  last:=1;                         % Its highest-order digit is number 1.for n:=1 to FactorialLimit do% Step through producing 1!, 2!, 3!, 4!, etc.    carry:=0;                       % Start a multiply by n.for i:=1 to last do% Step along every digit.    d:=digit[i]*n + carry;         % The classic multiply.    digit[i]:=d mod Base;          % The low-order digit of the result.    carry:=d div Base;             % The carry to the next digit.next i;   while carry > 0                 % Store the carry in the big number.            if last >= Limit then croak("Overflow!");  % If possible!    last:=last + 1;                % One more digit.    digit[last]:=carry mod Base;   % Placed.    carry:=carry div Base;         % The carry reduced.Wend% With n > Base, maybe > 1 digit extra.   text:=" ";                      % Now prepare the output.for i:=1 to last do% Translate from binary to text.    text[Limit - i + 1]:=tdigit[digit[i]];  % Reversing the order.next i;                         % Arabic numerals put the low order last.Print text," = ",n,"!";         % Print the result!next n;                          % On to the next factorial up.END;`

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 d 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 n is not itself limited to a single digit. This has the consequence that the method will fail for n > 3200 or so. In a more general implementation, n 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 numbersReach of computer integers
1 =1!
2 =2!
6 =3!
24 =4!
120 =5!8-bit255
720 =6!
5040 =7!
40320 =8!16-bit65535
3 62880 =9!
36 28800 =10!
399 16800 =11!
4790 01600 =12!32-bit42949 67295
62270 20800 =13!
8 71782 91200 =14!
130 76743 68000 =15!
2092 27898 88000 =16!
35568 74280 96000 =17!
6 40237 37057 28000 =18!
121 64510 04088 32000 =19!
2432 90200 81766 40000 =20!64-bit18446 74407 37095 51615
51090 94217 17094 40000 =21!
11 24000 72777 76076 80000 =22!
258 52016 73888 49766 40000 =23!
6204 48401 73323 94393 60000 =24!
1 55112 10043 33098 59840 00000 =25!
40 32914 61126 60563 55840 00000 =26!
1088 88694 50418 35216 07680 00000 =27!
30488 83446 11713 86050 15040 00000 =28!
8 84176 19937 39701 95454 36160 00000 =29!
265 25285 98121 91058 63630 84800 00000 =30!
8222 83865 41779 22817 72556 28800 00000 =31!
2 63130 83693 36935 30167 21801 21600 00000 =32!
86 83317 61881 18864 95518 19440 12800 00000 =33!
2952 32799 03960 41408 47618 60964 35200 00000 =34!128-bit3402 82366 92093 84634 63374 60743 17682 11455
1 03331 47966 38614 49296 66651 33752 32000 00000 =35!

This implementation could make more effective use of the computer's built in arithmetic. A simple escalation would be to use base 100 (with corresponding changes to the translation process for output), or, with sufficiently wide computer variables (such as 32-bit integers) we could use larger bases, such as 10,000. Working in a power-of-2 base closer to the computer's built-in integer operations offers advantages, although conversion to a decimal base for output becomes more difficult. On typical modern computers, additions and multiplications take constant time independent of the values of the operands (so long as the operands fit in single machine words), so there are large gains in packing as much of a bignumber as possible into each element of the digit array. The computer may also offer facilities for splitting a product into a digit and carry without requiring the two operations of mod and div as in the example, and nearly all arithmetic units provide a carry flag which can be exploited in multiple-precision addition and subtraction. This sort of detail is the grist of machine-code programmers, and a suitable assembly-language bignumber routine can run much faster than the result of the compilation of a high-level language, which does not provide access to such facilities.

For a single-digit multiply the working variables must be able to hold the value (base-1)2 + carry, where the maximum value of the carry is (base-1). Similarly, the variables used to index the digit array are themselves limited in width. A simple way to extend the indices would be to deal with the bignumber's digits in blocks of some convenient size so that the addressing would be via (block i, digit j) where i and j would be small integers, or, one could escalate to employing bignumber techniques for the indexing variables. Ultimately, machine storage capacity and execution time impose limits on the problem size.

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 string 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 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 (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 .

Related Research Articles

Arithmetic is a branch of mathematics that consists of the study of numbers, especially concerning the properties of the traditional operations on them—addition, subtraction, multiplication, division, exponentiation and extraction of roots. Arithmetic is an elementary part of number theory, and number theory is considered to be one of the top-level divisions of modern mathematics, along with algebra, geometry, and analysis. The terms arithmetic and higher arithmetic were used until the beginning of the 20th century as synonyms for number theory, and are sometimes still used to refer to a wider part of number theory.

In computing, floating-point arithmetic (FP) is arithmetic using formulaic representation of real numbers as an approximation to support a trade-off between range and precision. For this reason, floating-point computation is often used in systems with very small and very large real numbers that require fast processing times. In general, a floating-point number is represented approximately with a fixed number of significant digits and scaled using an exponent in some fixed base; the base for the scaling is normally two, ten, or sixteen. A number that can be represented exactly is of the following form:

A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The values are usually used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter storage addressing.

In computer science, an integer is a datum of integral data type, a data type that represents some range of mathematical integers. Integral data types may be of different sizes and may or may not be allowed to contain negative values. Integers are commonly represented in a computer as a group of binary digits (bits). The size of the grouping varies so the set of integer sizes available varies between different types of computers. Computer hardware nearly always provide a way to represent a processor register or memory address as an integer.

Multiplication is one of the four elementary mathematical operations of arithmetic, with the other ones being addition, subtraction and division. The result of a multiplication operation is called a product.

A computer number format is the internal representation of numeric values in digital device hardware and software, such as in programmable computers and calculators. Numerical values are stored as groupings of bits, such as bytes and words. The encoding between numerical values and bit patterns is chosen for convenience of the operation of the computer; the encoding used by the computer's instruction set generally requires conversion for external use, such as for printing and display. Different types of processors may have different internal representations of numerical values and different conventions are used for integer and real numbers. Most calculations are carried out with number formats that fit into a processor register, but some software systems allow representation of arbitrarily large numbers using multiple words of memory.

A multiplication algorithm is an algorithm to multiply two numbers. Depending on the size of the numbers, different algorithms are used. Efficient multiplication algorithms have existed since the advent of the decimal system.

In computer science and computer programming, a data type or simply type is an attribute of data which tells the compiler or interpreter how the programmer intends to use the data. Most programming languages support basic data types of integer numbers, floating-point numbers, characters and Booleans. A data type constrains the values that an expression, such as a variable or a function, might take. This data type defines the operations that can be done on the data, the meaning of the data, and the way values of that type can be stored. A data type provides a set of values from which an expression may take its values.

Rounding means replacing a number with an approximate value that has a shorter, simpler, or more explicit representation. For example, replacing \$23.4476 with \$23.45, the fraction 312/937 with 1/3, or the expression 2 with 1.414.

Two's complement is a mathematical operation on binary numbers, and is an example of a radix complement. It is used in computing as a method of signed number representation.

In numerical analysis, the Kahan summation algorithm, also known as compensated summation, significantly reduces the numerical error in the total obtained by adding a sequence of finite-precision floating-point numbers, compared to the obvious approach. This is done by keeping a separate running compensation.

In computing, a fixed-point number representation is a real data type for a number that has a fixed number of digits after the radix point. Fixed-point number representation can be compared to the more complicated floating-point number representation.

In modular arithmetic computation, Montgomery modular multiplication, more commonly referred to as Montgomery multiplication, is a method for performing fast modular multiplication. It was introduced in 1985 by the American mathematician Peter L. Montgomery.

The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971. The run-time bit complexity is, in Big O notation, for two n-digit numbers. The algorithm uses recursive Fast Fourier transforms in rings with 2n+1 elements, a specific type of number theoretic transform.

In computer programming, an integer overflow occurs when an arithmetic operation attempts to create a numeric value that is outside of the range that can be represented with a given number of digits – either higher than the maximum or lower than the minimum representable value.

A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software.

Binary scaling is a computer programming technique used typically in embedded C, DSP and assembler programs to implement non-integer operations by using the native integer arithmetic of the processor.

Some programming languages provide a built-in (primitive) rational data type to represent rational numbers like 1/3 and -11/17 without rounding, and to do arithmetic on them. Examples are the `ratio` type of Common Lisp, and analogous types provided by most languages for algebraic computation, such as Mathematica and Maple. Many languages that do not have a built-in rational type still provide it as a library-defined type.

Floating-point error mitigation is the minimization of errors caused by the fact that real numbers cannot, in general, be accurately represented in a fixed space. By definition, floating-point error cannot be eliminated, and, at best, can only be managed.

References

1. Jacqui Cheng (May 23, 2007). "Researchers: 307-digit key crack endangers 1024-bit RSA".
2. "Archived copy". Archived from the original on 2012-04-01. Retrieved 2012-03-31.CS1 maint: archived copy as title (link) recommends important RSA keys be 2048 bits (roughly 600 digits).
3. Laurent Fousse (2006). Intégration numérique avec erreur bornée en précision arbitraire. Modélisation et simulation (Report) (in French). Université Henri Poincaré - Nancy I.
4. R. K. Pathria (1962). "A Statistical Study of the Randomness Among the First 10,000 Digits of Pi". Mathematics of Computation. 16 (78): 188–197. doi:. Retrieved 2014-01-10. 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.