In
computer scienceComputer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems. It is frequently described as the systematic study of algorithmic processes that create, describe and transform...
,
arbitrary-precision arithmetic is a technique whereby
calculationA calculation is a deliberate process for transforming one or more inputs into one or more results, with variable change.The term is used in a variety of senses, from the very definite arithmetical calculation of using an algorithm to the vague heuristics of calculating a strategy in a competition...
s are performed on numbers whose
digitIn mathematics and computer science, a digit is a symbol used in numerals , to represent numbers, in positional numeral systems...
s of
precisionThe precision of a value describes the number of digits that are used to express that value. In a scientific setting this would be the total number of digits or, less commonly, the number of fractional digits or decimal places...
are limited only by the available memory of the host system. This contrasts with the faster
fixed-point arithmeticIn 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...
found in most
ALU hardwareIn computing, an arithmetic logic unit is a digital circuit that performs arithmetic and logical operations. The ALU is a fundamental building block of the central processing unit of a computer, and even the simplest microprocessors contain one for purposes such as maintaining timers...
, which typically offers between 6 and 16 decimal digits. It is also called
bignum arithmetic, and sometimes even "infinite-precision arithmetic" (which is a misnomer, since the number of digits is both finite and bounded in practice).
Several modern programming languages have built-in support for bignums, and others have libraries available for bignum
integerThe integers are natural numbers including 0 and their negatives . They are numbers that can be written without a fractional or decimal component, and fall within the set {.....
and floating-point math. Rather than store values as a fixed number of binary
bitIn computing and telecommunications a bit is a basic unit of information storage and communication . It is the maximum amount of information that can be stored by a device or other physical system that can normally exist in only two distinct states...
s related to the size of the
processor registerIn computer architecture, a processor register is a small amount of storage available on the CPU whose contents can be accessed more quickly than storage available elsewhere. Most, but not all, modern computers adopt the so-called load-store architecture...
, these implementations typically use variable-length arrays of digits. Since division can introduce infinitely
repeating decimalA decimal representation of a real number is called a repeating decimal if at some point it becomes periodic: there is some finite sequence of digits that is repeated indefinitely. For example, the decimal representation of becomes periodic just after the decimal point, repeating the...
s, they often store
rational numberIn mathematics, a rational number is any number that can be expressed as the quotient a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer corresponds to a rational number. The set of all rational numbers is usually denoted .Formally each rational...
s as an arbitrary-precision integer for both the
numeratorNumerator may refer to:* A numeral used to indicate a count, particularly of the equal parts in a fraction. A numerator is the number on top of the fraction. For example, in the fraction , also written 3/4, 3 is the numerator and 4 is the denominator....
and denominator, with the
greatest common divisorIn mathematics, the greatest common divisor , also known as the greatest common factor , the greatest common denominator, or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.This notion can be extended to...
divided out.
Arbitrary precision is used in applications where the speed of arithmetic is not a limiting factor, or where precise results with very large numbers is required. It should not be confused with the
symbolic computationSymbolic computation or algebraic computation, relates to the use of machines, such as computers, to manipulate mathematical equations and expressions in symbolic form, as opposed to manipulating the approximations of specific numerical quantities represented by those symbols...
provided by many
computer algebra systemA computer algebra system is a software program that facilitates symbolic mathematics. The core functionality of a CAS is manipulation of mathematical expressions in symbolic form.-Symbolic manipulations:...
s, which represent numbers by expressions such as , and can thus
represent any
computable numberIn mathematics, particularly theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers or the computable reals, are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm...
with infinite precision. Yet symbolic computation can only
evaluate to a finite precision, since the expression must be computed with arbitrary-precision arithmetic.
Applications
A common application is
public-key cryptographyPublic-key cryptography is a cryptographic approach, employed by many cryptographic algorithms and cryptosystems, whose distinguishing characteristic is the use of asymmetric key algorithms instead of or in addition to symmetric key algorithms...
(such as that in every modern
Web browserA web browser is a software application for retrieving, presenting, and traversing information resources on the World Wide Web. An information resource is identified by a Uniform Resource Identifier and may be a web page, image, video, or other piece of content...
), whose algorithms commonly employ arithmetic with integers of hundreds or thousands of digits. Another is in human-centric applications where artificial limits and overflows would be inappropriate. It is also useful for checking the results of fixed-precision calculations, and for determining the best possible value for coefficients needed in formulae (the √⅓ that appears in Gaussian integration, for example).
Arbitrary precision arithmetic is also used to compute fundamental
mathematical constantA mathematical constant is a number, usually a real number, that arises naturally in mathematics. Unlike physical constants, mathematical constants are defined independently of physical measurement....
s such as
πPi or π is a mathematical constant whose value is the ratio of any circle's circumference to its diameter in Euclidean space; this is the same value as the ratio of a circle's area to the square of its radius. The symbol π was first proposed by the Welsh mathematician William Jones in 1706...
to millions or more digits and to analyze the properties of the digit strings (e.g. ), 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
FractalA fractal is "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...
images with an extremely high magnification, such as those found in the
Mandelbrot setIn mathematics the Mandelbrot set, named after Benoît Mandelbrot, is a set of points in the complex plane, the boundary of which forms a fractal...
.
Arbitrary-precision arithmetic can also be used to avoid
overflowThe term arithmetic overflow or simply overflow has the following meanings.# In a computer, the condition that occurs when a calculation produces a result that is greater in magnitude than that which a given register or storage location can store or represent.# In a computer, the amount by which a...
, which is an inherent limitation of fixed-precision arithmetic. Just like a 4-digit odometer which rolls around from 9999 to 0000, a fixed-precision integer can exhibit
wraparound if numbers grow too large to represent at the fixed level of precision. Some processors can 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 1 to 65535 yields 65535 — see
saturation arithmeticSaturation arithmetic is a version of arithmetic in which all operations such as addition and multiplication are limited to a fixed range between a minimum and maximum value. If the result of an operation is greater than the maximum it is set to the maximum, while if it is below the minimum it is...
.) Some processors can generate an
exceptionException handling is a programming language construct or computer hardware mechanism designed to handle the occurrence of exceptions, special conditions that change the normal flow of program execution....
if an arithmetic result exceeds the available precision. Where necessary, the exception can be caught and the operation can be restarted in software with arbitrary-precision operands.
Since many computers now routinely use 32-bit or even 64-bit integers, it can often be guaranteed that the integer numbers in a specific application will never grow large enough to cause an overflow. Though as time passes the exact nature of the constraint can be forgotten, as in implementations of the Binary search method which often employ the form (L + R)/2; this means that for correct functioning the
sum of L and R is limited to the machine word size (eg. 32 or 64 bits), not just the individual variables.
Some programming languages such as
LispLisp is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older. Like Fortran, Lisp has changed a great deal...
,
RexxREXX is an interpreted programming language which was developed at IBM. It is a structured high-level programming language which was designed to be both easy to learn and easy to read...
,
PythonPython is a general-purpose high-level programming language. Its design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
,
PerlPerl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall, a linguist working as a systems administrator for NASA, in 1987, as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone...
and
RubyRuby is a dynamic, reflective, general purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was initially developed and designed by Yukihiro "Matz" Matsumoto...
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 the panoply of types needed 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 arithmeticIn computing, an arithmetic logic unit is a digital circuit that performs arithmetic and logical operations. The ALU is a fundamental building block of the central processing unit of a computer, and even the simplest microprocessors contain one for purposes such as maintaining timers...
whereas the former must be implemented in software. There are exceptions, as certain "variable word length" machines of the 1950s and 1960s, notably the IBM 1401 and the Honeywell "Liberator" series, could manipulate numbers bound only by available storage, with an extra bit that delimited the value. 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.
Numbers can be stored in a
fixed-pointIn 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...
format, or in a floating-point format as a
significandThe significand is the part of a floating-point number that contains its significant digits. Depending on the interpretation of the exponent, the significand may be considered to be an integer or a fraction.-Examples:...
multiplied by an arbitrary exponent. However, since division almost immediately introduces infinitely repeating sequences of digits (such as 4/7 in decimal), 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
numeratorNumerator may refer to:* A numeral used to indicate a count, particularly of the equal parts in a fraction. A numerator is the number on top of the fraction. For example, in the fraction , also written 3/4, 3 is the numerator and 4 is the denominator....
and for the denominator, with the
greatest common divisorIn mathematics, the greatest common divisor , also known as the greatest common factor , the greatest common denominator, or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.This notion can be extended to...
divided out. Unfortunately, arithmetic with rational numbers can become unwieldy very swiftly: 1/99 - 1/100 = 1/9900, and if 1/101 is then added the result is 10001/999900.
Bounding the size of arbitrary-precision numbers is not only the total storage available, but the variables used by the software to index the digit strings. These are typically themselves limited in size.
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
complexityComputational complexity theory is a branch of the theory of computation in computer science that focuses on classifying computational problems according to their inherent difficulty. In this context, a computational problem is understood to be a task that is in principle amenable to being solved...
for large
N.
The simplest algorithms are for
additionAddition is the mathematical process of combining quantities. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples. Therefore, 3 + 2 = 5...
and
subtractionSubtraction is one of the four basic arithmetic operations; it is the inverse of addition, meaning that if we start with any number and add any number and then subtract the same number we added, we return to the number we started with...
, where one simply adds or subtracts the digits in sequence, carrying as necessary, which yields an
O(
N) algorithm (see
big O notationIn mathematics, computer science, and related fields, big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions...
).
For
multiplicationMultiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
, the most straightforward algorithms used for multiplying numbers by hand (as taught in primary school) requires operations, but
multiplication algorithmA multiplication algorithm is an algorithm to multiply two numbers. Depending on the size of the numbers, different algorithms are in use...
s that achieve complexity have been devised, such as the
Schönhage-Strassen algorithmThe 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, O, while the arithmetic complexity is O...
, based on
fast Fourier transformA fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex-number arithmetic to group theory and number theory; this article gives an overview of...
s, and there are also algorithms with slightly worse complexity but with sometimes superior real-world performance for smaller
N.
For a list of algorithms along with complexity estimates, see:
Computational complexity of mathematical operationsThe following tables list the computational complexity of various algorithms for common mathematical operations.Here, complexity refers to the time complexity of performing computations on a multitape Turing machine...
Example
The calculation of
factorialIn mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...
s produces very large numbers very swiftly. This is not a problem for their usage in many formulae (such as
Taylor seriesIn mathematics, the Taylor series is a representation of a function as an infinite sum of terms calculated from the values of its derivatives at a single point. It may be regarded as the limit of the Taylor polynomials. Taylor series are named after the English mathematician Brook Taylor...
) because they appear along with other terms so that given careful attention to the order of evaluation the net calculation value is not troublesome. If approximate values of factorial numbers are desired,
Stirling's approximationIn mathematics, Stirling's approximation is an approximation for large factorials. It is named after James Stirling.The formula as typically used in applications is...
gives good results. If exact values are of interest, then the integer limit is soon exceeded. Even floating-point approximations soon exceed the maximum floating-point value possible, to the degree that the calculations should be recast into using the log of the number.
But if exact values for large factorials are desired, then special software is required, somewhat as in the pseudocode that follows, which implements the classic primary school 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.
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;
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 365 do
carry:=0; %Start a multiply.
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,"!";
next n;
END;
With the example in view, a number of details can be described. The most important is the choice of the representation of the big number. In this case, only integer values are required for factorials, so a fixed-point scheme is adequate. The powers of the base are zero and upwards, so it is convenient to have successive elements of the array represent higher powers. The computer language may not enable a convenient choice of the array bounds (for example, the lower bound might have to be one, always, or zero, always) and the requirements of the calculation in general might not involve a permitted bound, so this example proceeds with an array starting from one, not zero, to demonstrate the simple issues of accountancy. That the index into the digit array corresponds to a certain power of the base is not directly utilised as a part of the method.
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 previous 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 be a single-digit base ten number. This has the consequence that the method will fail for
n > 3200 or so, not a pressing limit in this example. In general,
n would be a multi-digit big number also. A second consequence of the shortcut is that after the multi-digit multiply has been completed, the last value of
carry must be carried into higher-order digits beyond what was the upper limit of the previous number because it may be carrying multiple digits not just the single digit that would otherwise be normal.
Flowing from the choice of the base for the bignumber comes the issue of presenting its value. Because the base is 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 a hundred and twenty-three would appear as "321") because of the first choice for the representation of the bignumber. The tradition for Arabic numbers is the other way around, so they could be printed in reverse order. But that would present the number with leading zeroes ("00000...000123") which may not be appreciated, so the final decision is to build the representation in a text variable and then print that. The first few results (with many leading spaces removed) are:
Reach of computer numbers.
1 = 1!
2 = 2!
6 = 3!
24 = 4!
120 = 5! 8-bit unsigned
720 = 6!
5040 = 7!
40320 = 8! 16-bit unsigned
362880 = 9!
3628800 = 10!
39916800 = 11!
479001600 = 12! 32-bit unsigned
6227020800 = 13!
87178291200 = 14!
1307674368000 = 15!
20922789888000 = 16!
355687428096000 = 17!
6402373705728000 = 18!
121645100408832000 = 19!
2432902008176640000 = 20! 64-bit unsigned
51090942171709440000 = 21!
1124000727777607680000 = 22!
25852016738884976640000 = 23!
620448401733239439360000 = 24!
15511210043330985984000000 = 25!
403291461126605635584000000 = 26!
10888869450418352160768000000 = 27!
304888344611713860501504000000 = 28!
8841761993739701954543616000000 = 29!
265252859812191058636308480000000 = 30!
8222838654177922817725562880000000 = 31!
263130836933693530167218012160000000 = 32!
8683317618811886495518194401280000000 = 33!
295232799039604140847618609643520000000 = 34! 128-bit unsigned
10333147966386144929666651337523200000000 = 35!
More serious attempts would try to use the available arithmetic of the computer more efficiently. A simple escalation would be to base 100 (with corresponding changes to the translation process for output), or, bigger computer variables (such as 32-bit integers) could be used so as to enable larger bases, such as 10,000. Conversion from non-decimal bases to a decimal base for output is a significant computation. Nevertheless, working in bases closer to the computer's built-in integer operations offers advantages. Operations on an integer holding a value such as six take just as long as the same operation on an integer holding a larger value, so there are large gains in packing as much of a bignumber into each element of the digit array as possible. 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. For instance, the
IBM1130The IBM 1130 Computing System was introduced in 1965. It was IBM's least-expensive computer to date, and was aimed at price-sensitive, computing-intensive technical markets like education and engineering. It succeeded the IBM 1620 in that market segment. The IBM 1800 was a process control variant...
integer multiply of 16-bit integers (actually of a 32-bit accumulator and extension register pair, with a nominated 16-bit word) produced a 32-bit result which could be treated as two separate 16-bit words, thus if the bignumber base was 65536 the
carry would be in the high-order sixteen bits, and the
digit would be in the lower-order sixteen bits. No
mod and
div operations would be required to separate them.
This sort of detail is the grist of machine-code programmers, and a suitable bignumber routine would run orders of magnitude faster than the result of the compilation of a high-level language, which do not offer similar facilities. Even so, it may be possible to juggle 16-bit and 32-bit variables in cunning ways, but the tricks (essentially, arranging that a 32-bit variable overlays the same storage as two 16-bit variables) are frowned upon by computer language purists. Thus the EQUIVALENCE statement of
FortranFortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing...
and the OVERLAY statement of Pl/1 are deprecated.
For a single-digit multiply the working variables must be able to hold the value (base -1)² + carry, where the maximum value of the carry is (base - 1). Notice that the IBM1130 offered a working register of 32 bits for 16-bit arithmetic so that many calculations whose intermediate results exceeded the 16-bit limit nevertheless worked; in a high-level language, if the bignumber's digit array were of unsigned 16-bit integers and the base 65536, the maximum result of a digit multiply would not exceed 4,294,901,760 but this exceeds the capacity of a 32-bit signed integer which is 2³¹ - 1 = 2,147,483,647. The high-level language may not offer a 32-bit unsigned integer as a variable (limit 2³² - 1 = 4,294,967,295), even if the computer's internal arithmetic register allows this or is bigger still. Or, if 32-bit unsigned integers
are available, what then of the required 64-bit unsigned integers?
Similarly, the variables used to index the digit array are themselves limited to sixteen (or thirty-two bits, etc.); even if sixty-four bit integers were available there is still an upper limit aside from storage availability. A simple approach 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. Either way, storage limits await: the entire observable universe contains no more than an estimated nuclear particles.
Choosing instead a base of 256 has the advantage of simplicity, and moreover, it is quite possible to check for the correct function of the basic arithmetic operations on
all possible digit combinations. Errors in computer hardware are not unknown. Since the prime purpose for slow but exact or at least high-precision computation is to obtain definitive results, some sort of assurance is helpful.
History
An early widespread implementation was available via the
IBM 1620The IBM 1620 was announced by IBM on October 21, 1959 and marketed as an inexpensive "scientific computer". After a total production of about two thousand machines, it was withdrawn on November 19, 1970...
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 or floating-point arithmetic on digit strings of a length that could be from two to whatever memory was available. (The mantissa of floating-point numbers was restricted to 100 digits or fewer, and the exponent of floating-point numbers was restricted to two digits only.) The largest memory supplied offered sixty thousand digits, however
FortranFortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing...
compilers for the 1620 settled on fixed sizes such as ten (though it could be specified on a control card if the default was not satisfactory).
IBM's first business computer, the
IBM 702The IBM 702 was announced September 25, 1953 and withdrawn October 1, 1954, but the first production model was not installed until July 1955...
(a
vacuum tubeIn electronics, a vacuum tube, electron tube , thermionic valve, or valve is a device used to amplify, switch, otherwise modify, or create an electrical signal by controlling the movement of electrons in a low-pressure space...
machine), implemented integer arithmetic
entirely in hardware on digit strings of any length from one to 511 digits. The earliest widespread software implementation of arbitrary precision arithmetic was probably that in
MaclispMACLISP is a dialect of the Lisp programming language. It originated at MIT's Project MAC in the late 1960s and was based on Lisp 1.5. Richard Greenblatt was the main developer of the original codebase for the PDP-6; Jonl White was responsible for its later maintenance and development...
. Later, around 1980, the VAX/VMS and VM/CMS
operating systemAn operating system is an interface between hardware and user which is responsible for the management and coordination of activities and the sharing of the resources of the computer that acts as a host for computing applications run on the machine. As a host, one of the purposes of an operating...
s offered bignum facilities as a collection of string functions in the one case and in the
EXEC 2EXEC 2 is an interpreted, command procedure control, computer programming language used by the EXEC 2 Processor supplied with the IBM Virtual Machine/Conversational Monitor System operating system....
and
REXXREXX is an interpreted programming language which was developed at IBM. It is a structured high-level programming language which was designed to be both easy to learn and easy to read...
languages in the other.
Stand-alone application softwareApplication software is a computer program that functions and is operated by means of a computer, with the purpose of supporting or improving the software user's work. In other words, it is the subclass of computer software that employs the capabilities of a computer directly and thoroughly to a...
Software that supports arbitrary precision computations:
- Mathematica
Mathematica is a computational software program used in scientific, engineering, and mathematical fields and other areas of technical computing...
, and several other computer algebra software include arbitrary-precision arithmetic. Mathematica employs GMPThe GNU Multiple-Precision Library, also known as GMP, is a free library for arbitrary-precision arithmetic, operating on signed integers, rational numbers, and floating point numbers...
for approximate number computation.
- PARI/GP
PARI/GP is a computer algebra system with the main aim of facilitating number theory computations. As of July 10, 2008, the stable version is 2.3.4; and a development version, 2.4.3 is available. It is free software since Version 2.1.0 and is distributed under the terms of the GNU General Public...
, an open sourceOpen source is an approach to the design, development, and distribution of software, offering practical accessibility to a software's source code. Some consider open source as one of various possible design approaches, while others consider it a critical strategic element of their operations...
computer algebra system that supports arbitrary precision.
- bc
bc is "an arbitrary precision calculator language" with syntax similar to the C programming language. It is generally used by typing the command bc on a Unix command prompt and entering a mathematical expression, such as * 2, whereupon 8 will be output.There are currently two main...
an arbitrary-precision math program that comes standard on most *nixA Unix-like operating system is one that behaves in a manner similar to a Unix system, while not necessarily conforming to or being certified to any version of the Single UNIX Specification....
systems.
- Maxima (software): a Computer algebra system
A computer algebra system is a software program that facilitates symbolic mathematics. The core functionality of a CAS is manipulation of mathematical expressions in symbolic form.-Symbolic manipulations:...
whose "bignum" integers are directly inherited from its implementation language Common LispCommon Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . Developed to standardize the divergent variants of Lisp which predated it, it is not an implementation but rather a language specification...
.
- Ultra Fractal
Ultra Fractal is a fractal generation and rendering software application. The program works using a similar paradigm to Photoshop, allowing multiple layers to be combined using layer blending modes, transformations and custom fractal formulas....
: a fractal generation program.
- Fractint
Fractint is a freeware software package that can render and display many kinds of fractals. Its name comes from the words fractal and integer, since the first versions of it computed fractals by using only integer arithmetic , which led to much faster rendering on x86 computers without math...
is a freewareFreeware is computer software that is available for use at no cost or for an optional fee.The opposite of Freeware is Payware.-History:...
open sourceOpen source is an approach to the design, development, and distribution of software, offering practical accessibility to a software's source code. Some consider open source as one of various possible design approaches, while others consider it a critical strategic element of their operations...
software package that can render and display many kinds of fractalA fractal is "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...
s
- Virtual Calc 2000: arbitrary-precision and arbitrary-base calculator for Windows
- Calc C-style arbitrary precision calculator (LGPL2)
- SpeedCrunch is an open source
Open source is an approach to the design, development, and distribution of software, offering practical accessibility to a software's source code. Some consider open source as one of various possible design approaches, while others consider it a critical strategic element of their operations...
cross-platformIn computing, cross-platform is a term used to refer to computer software or computing methods and concepts that are implemented and inter-operate on multiple computer platforms...
high precision calculator
- TTCalc an open source bignum mathematical calculator (TTMath library).
Online tools
Software that supports arbitrary precision computations available through a web browser:
Libraries
Arbitrary-precision arithmetic in most computer software is implemented by calling an external
libraryIn computer science, a library is a collection of subroutines or classes used to develop software. Libraries contain code and data that provide services to independent programs. This allows the sharing and changing of code and data in a modular fashion. Some executables are both standalone programs...
that provides
data typeA data type in programming languages is a set of values and the operations on those values.-Overview:Almost all programming languages explicitly include the notion of data type, though different languages may use different terminology...
s and
subroutineIn computer science, a subroutine or subprogram is a portion of code within a larger program, which performs a specific task and is relatively independent of the remaining code....
s 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 (
RationalsIn mathematics, a rational number is any number that can be expressed as the quotient a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer corresponds to a rational number. The set of all rational numbers is usually denoted .Formally each rational...
) and some can fully represent real numbers.
| Package / Library Name |
Number Type |
Language |
License |
| apfloat |
Decimal floats, integers, rationals In mathematics, a rational number is any number that can be expressed as the quotient a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer corresponds to a rational number. The set of all rational numbers is usually denoted .Formally each rational...
, and complexA complex number, in mathematics, is a number comprising a real number and an imaginary number; it can be written in the form a + bi, where a and b are real numbers, and i is the standard imaginary unit, having the property that i 2 = −1...
|
Java Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
and C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
|
LGPL The GNU Lesser General Public License or LGPL is a free software license published by the Free Software Foundation . It was designed as a compromise between the strong-copyleft GNU General Public License or GPL and permissive licenses such as the BSD licenses and the MIT License...
and FreewareFreeware is computer software that is available for use at no cost or for an optional fee.The opposite of Freeware is Payware.-History:...
|
| ARPREC and MPFUN |
Integers, binary floats, complex binary floats |
C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
with C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
and FortranFortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing...
bindings |
BSD |
| Base One Number Class |
Decimal floats |
C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
|
Proprietary |
| bbnum library |
Integers and floats |
Assembler Assembly languages are a family of low-level languages for programming computers, microprocessors, microcontrollers, and other integrated circuits. They implement a symbolic representation of the numeric machine codes and other constants needed to program a particular CPU architecture...
and C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
|
New BSD |
| phpseclib |
Decimal floats |
PHPPHP, or PHP: Hypertext Preprocessor, is a widely used, general-purpose scripting language that was originally designed for web development, to produce dynamic web pages. It can be embedded into HTML and generally runs on a web server, which needs to be configured to process PHP code and create web...
|
LGPL |
| BigDigits |
Naturals |
C C is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
|
Freeware Freeware is computer software that is available for use at no cost or for an optional fee.The opposite of Freeware is Payware.-History:...
http://www.di-mgt.com.au/bigdigitsCopyright.txt |
| CLN, a Class Library for Numbers CLN is a free library for arbitrary precision arithmetic. It operates on signed integers, rational numbers, floating point numbers, complex numbers, modular numbers, and univariate polynomials...
|
Integers, rationals In mathematics, a rational number is any number that can be expressed as the quotient a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer corresponds to a rational number. The set of all rational numbers is usually denoted .Formally each rational...
, and complexA complex number, in mathematics, is a number comprising a real number and an imaginary number; it can be written in the form a + bi, where a and b are real numbers, and i is the standard imaginary unit, having the property that i 2 = −1...
|
C C is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
and C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
|
GPLThe GNU General Public License is a widely used free software license, originally written by Richard Stallman for the GNU project....
|
| Computable Real Numbers |
Reals |
Common Lisp Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . Developed to standardize the divergent variants of Lisp which predated it, it is not an implementation but rather a language specification...
|
|
| IMSL |
|
C C is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
|
Commercial |
| decNumber |
Decimals |
C C is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
|
ICU International Components for Unicode is an open source project of mature C/C++ and Java libraries for Unicode support, software internationalization and software globalization. ICU is widely portable to many operating systems and environments. It gives applications the same results on all...
licence (MIT licence) http://source.icu-project.org/repos/icu/icu/trunk/license.html |
| FMLIB |
Floats |
Fortran Fortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing...
|
|
| GNU Multi-Precision Library The GNU Multiple-Precision Library, also known as GMP, is a free library for arbitrary-precision arithmetic, operating on signed integers, rational numbers, and floating point numbers...
(and MPFRGNU MPFR is a portable C library for arbitrary-precision binary floating-point computation with correct rounding, based on GNU Multi-Precision Library. The computation is both efficient and has a well-defined semantics. It copies the good ideas from the ANSI/IEEE-754 standard for fixed-precision...
) |
Integers, rationals and floats |
C C is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
and C++ with bindings (GMPY,...) |
LGPL The GNU Lesser General Public License or LGPL is a free software license published by the Free Software Foundation . It was designed as a compromise between the strong-copyleft GNU General Public License or GPL and permissive licenses such as the BSD licenses and the MIT License...
|
| GNU Multi-Precision Library for .NET |
Integers |
C# / .NETThe Microsoft .NET Framework is a software framework that can be installed on computers running Microsoft Windows operating systems. It includes a large library of coded solutions to common programming problems and a virtual machine that manages the execution of programs written specifically for...
|
LGPL The GNU Lesser General Public License or LGPL is a free software license published by the Free Software Foundation . It was designed as a compromise between the strong-copyleft GNU General Public License or GPL and permissive licenses such as the BSD licenses and the MIT License...
|
| GNU Multi-Precision Library for Eiffel |
Integers and reals |
Eiffel Eiffel is an ISO-standardized, object-oriented programming language designed to enable programmers to efficiently develop extensible, reusable, reliable software. Eiffel is used in academia as a language for teaching computer-programming principles. Eiffel is used in the finance, aerospace,...
|
LGPL The GNU Lesser General Public License or LGPL is a free software license published by the Free Software Foundation . It was designed as a compromise between the strong-copyleft GNU General Public License or GPL and permissive licenses such as the BSD licenses and the MIT License...
|
| HugeCalc |
Integers |
C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
and AssemblerAssembler may refer to:* Assembler for an assembly language, a computer program to translate between lower-level representations of computer programs* Assembler , a program to perform genome assembly...
|
Proprietary |
| IMath |
Integers and rationals |
C C is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
|
Freeware Freeware is computer software that is available for use at no cost or for an optional fee.The opposite of Freeware is Payware.-History:...
|
| IntX |
Integers |
C# / .NETThe Microsoft .NET Framework is a software framework that can be installed on computers running Microsoft Windows operating systems. It includes a large library of coded solutions to common programming problems and a virtual machine that manages the execution of programs written specifically for...
|
New BSD |
| JScience LargeInteger |
Integers |
Java Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
|
|
| LibTomMath |
Integers |
C C is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
and C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
|
Public domain The public domain is a range of abstract materials—commonly referred to as intellectual property—which are not owned or controlled by anyone. The term indicates that these materials are therefore "public property", and available for anyone to use for any purpose...
|
| LiDIA |
Integers |
C C is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
and C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
|
Free for non-commercial use |
| MAPM |
Integers and decimal floats |
C C is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
(bindings for C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
and Lua) |
Freeware Freeware is computer software that is available for use at no cost or for an optional fee.The opposite of Freeware is Payware.-History:...
|
| MIRACL MIRACL is an arbitrary-precision arithmetic software package developed by Shamus Software. It is often used in encryption and number theory programs...
|
Integers and rationals |
C C is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
and C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
|
Free for non-commercial use |
| MPI |
Integers |
C C is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
|
LGPL |
| MPArith |
Integers, floats, and rationals |
Pascal / Delphi Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...
|
zlib |
| mpmath |
Floats, complex floats |
PythonPython is a general-purpose high-level programming language. Its design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
|
New BSD |
| NTL |
Integers |
C C is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
and C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
|
GPLThe GNU General Public License is a widely used free software license, originally written by Richard Stallman for the GNU project....
|
| TTMath library |
Integers and binary floats |
Assembler Assembly languages are a family of low-level languages for programming computers, microprocessors, microcontrollers, and other integrated circuits. They implement a symbolic representation of the numeric machine codes and other constants needed to program a particular CPU architecture...
and C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
|
New BSD |
| vecLib.framework |
Integers |
C C is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
|
Proprietary |
| W3b.Sine |
Decimal floats |
C# / .NETThe Microsoft .NET Framework is a software framework that can be installed on computers running Microsoft Windows operating systems. It includes a large library of coded solutions to common programming problems and a virtual machine that manages the execution of programs written specifically for...
|
New BSD |
Languages
Programming languages that supports arbitrary precision computations, either built-in, or in the standard library of the language:
- Common Lisp
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . Developed to standardize the divergent variants of Lisp which predated it, it is not an implementation but rather a language specification...
: The ANSI Common Lisp standard supports arbitrary precision integer, ratio and complex numbers.
- dc: the POSIX desk calculator
- Erlang: the built-in Integer datatype implements arbitrary-precision arithmetic.
- Haskell
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry.- History :...
: the built-in Integer datatype implements arbitrary-precision arithmetic.
- Java
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
: class java.math.BigInteger (integer), Class java.math.BigDecimal (decimal)
- OCaml: The Num library supports arbitrary-precision integers and rationals.
- Python
Python is a general-purpose high-level programming language. Its design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
: the built-in int (3.x) / long (2.x) integer type is of arbitrary precision. The Decimal class in the standard library module decimal has user definable precision.
- REXX
REXX is an interpreted programming language which was developed at IBM. It is a structured high-level programming language which was designed to be both easy to learn and easy to read...
: programming language (including Open Object Rexx and NetRexx)
- Ruby
Ruby is a dynamic, reflective, general purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was initially developed and designed by Yukihiro "Matz" Matsumoto...
: the built-in Bignum integer type is of arbitrary precision. The BigDecimal class in the standard library module bigdecimal has user definable precision.
- Scheme: R5RS encourages, and R6RS requires, that exact integers and exact rationals be of arbitrary precision.
- Scala
Scala may refer to:* Scala & Kolacny Brothers, a Belgian girls' choir* SCALA, the Student Chapter of the American Library Association* FF Scala and FF Scala Sans, typefaces by Dutch typeface designer Martin Majoor...
: Class BigInt.
- Smalltalk
Smalltalk is an object-oriented, dynamically typed, reflective programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human–computer symbiosis." It was designed and created in part for educational use, more so for constructionist...
: programming languages (including SqueakThe Squeak programming language is a Smalltalk implementation, derived directly from Smalltalk-80 by a group at Apple Computer that included some of the original Smalltalk-80 developers. Its development was continued by the same group at Walt Disney Imagineering, where it was intended for use in...
, Smalltalk/X, GNU SmalltalkGNU Smalltalk is an implementation of the Smalltalk programming language by the GNU Project.The implementation, unlike other Smalltalk environments, uses text files for program input and interprets the contents as Smalltalk code...
, Dolphin SmalltalkDolphin Smalltalk, or "Dolphin" for short , is an implementation of the Smalltalk programming language by Object Arts, targeted at the Microsoft Windows platform.The last major release was Dolphin Smalltalk X6, which comes in two versions:...
, etc.)