Arbitrary-precision arithmetic
Encyclopedia
In computer science
, arbitrary-precision arithmetic indicates that calculation
s are performed on numbers whose digit
s of precision
are limited only by the available memory of the host system. This contrasts with the faster fixed-precision arithmetic found in most ALU hardware
, which typically offers between 16 and 64 bit
s. Arbitrary-precision arithmetic is also called bignum arithmetic, multiple precision arithmetic, and sometimes "infinite-precision arithmetic".
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 binary bit
s 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 system
s, which represent numbers by expressions such as
, and can thus represent any computable number
with infinite precision.
(such as that in every modern Web browser
), whose algorithms commonly employ arithmetic with integers having hundreds or thousands of 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 the optimum value for coefficients needed in formulae, for example the √⅓ that appears in Gaussian integration.
Arbitrary precision arithmetic is also used to compute fundamental mathematical constant
s such as π
to millions or more digits and to analyze the properties of the digit strings 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 programmer can guarantee that the integer values in a specific application will not grow large enough to cause an overflow. However, as time passes and conditions change, the bounds of the guarantee can be exceeded. For example, implementations of the Binary search method that employ the form (L + R)/2 may function incorrectly when the sum of L and R exceeds the machine word size, although the individual variables themselves remain valid.
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.
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 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 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 O(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
operations, but multiplication algorithm
s that achieve
complexity have been devised, such as the Schönhage–Strassen algorithm, based on fast Fourier transform
s, and there are also algorithms with slightly worse complexity but with sometimes superior real-world performance for smaller N.
For division
, see: Division (digital)
.
For a list of algorithms along with complexity estimates, see: Computational complexity of mathematical operations
For examples in x86-assembly, see: External links.
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.
s can easily produce very large numbers. This is not a problem for their usage in many formulae (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 (see the table below). Even floating-point approximations can exceed the maximum representable floating-point value.
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.
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 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 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 we decided to build the representation in a space-padded text variable and then print that. The first few results 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!
We could try to use the available arithmetic of the computer more efficiently. 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 architectures, 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 architectures 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)² + 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.
(a vacuum tube
machine) of the mid 1950s, 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 Maclisp
. Later, around 1980, the VAX/VMS and VM/CMS operating system
s offered bignum facilities as a collection of string functions in the one case and in the EXEC 2
and REXX
languages 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 table
s) 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 sixty thousand digits, however Fortran
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.
that provides data type
s and subroutine
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 (Rationals
) and some can fully represent computable number
s, though only up to some storage limit. Fundamentally, Turing machines cannot represent all real numbers, as the cardinality of
exceeds the cardinality of 
.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, arbitrary-precision arithmetic indicates that calculation
Calculation
A 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 digit
Numerical digit
A digit is a symbol used in combinations to represent numbers in positional numeral systems. The name "digit" comes from the fact that the 10 digits of the hands correspond to the 10 symbols of the common base 10 number system, i.e...
s of precision
Precision (arithmetic)
The 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-precision arithmetic found in most ALU hardware
Arithmetic logic unit
In 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 16 and 64 bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s. Arbitrary-precision arithmetic is also called bignum arithmetic, multiple precision arithmetic, and sometimes "infinite-precision arithmetic".
Several modern programming languages have built-in support for bignums, and others have libraries available for arbitrary-precision integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
and floating-point math. Rather than store values as a fixed number of binary bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s related to the size of the processor register
Processor register
In computer architecture, a processor register is a small amount of storage available as part of a CPU or other digital processor. Such registers are addressed by mechanisms other than main memory and can be accessed more quickly...
, these implementations typically use variable-length arrays of digits.
Arbitrary precision is used in applications where the speed of arithmetic
Arithmetic
Arithmetic or arithmetics is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple day-to-day counting to advanced science and business calculations. It involves the study of quantity, especially as the result of combining numbers...
is not a limiting factor, or where precise results with very large numbers are required. It should not be confused with the symbolic computation
Symbolic computation
Symbolic 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 system
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:...
s, which represent numbers by expressions such as
, and can thus represent any computable numberComputable number
In 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.
Applications
A common application is public-key cryptographyPublic-key cryptography
Public-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...
(such as that in every modern Web browser
Web browser
A 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 having hundreds or thousands of 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 the optimum value for coefficients needed in formulae, for example the √⅓ that appears in Gaussian integration.
Arbitrary precision arithmetic is also used to compute fundamental mathematical constant
Mathematical constant
A mathematical constant is a special number, usually a real number, that is "significantly interesting in some way". Constants arise in many different areas of mathematics, with constants such as and occurring in such diverse contexts as geometry, number theory and calculus.What it means for a...
s such as π
Pi
' is a mathematical constant that is the ratio of any circle's circumference to its diameter. is approximately equal to 3.14. Many formulae in mathematics, science, and engineering involve , which makes it one of the most important mathematical constants...
to millions or more digits and to analyze the properties of the digit strings 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
Fractal
A fractal has been defined as "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 set
Mandelbrot set
The Mandelbrot set is a particular mathematical set of points, whose boundary generates a distinctive and easily recognisable two-dimensional fractal shape...
.
Arbitrary-precision arithmetic can also be used to avoid overflow
Arithmetic overflow
The 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. Similar to a 5-digit odometer
Odometer
An odometer or odograph is an instrument that indicates distance traveled by a vehicle, such as a bicycle or automobile. The device may be electronic, mechanical, or a combination of the two. The word derives from the Greek words hodós and métron...
'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
Saturation arithmetic
Saturation 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...
, 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
Exception handling
Exception 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 recovered from—for instance, the operation could be restarted in software using arbitrary-precision arithmetic.
In many cases, the programmer can guarantee that the integer values in a specific application will not grow large enough to cause an overflow. However, as time passes and conditions change, the bounds of the guarantee can be exceeded. For example, implementations of the Binary search method that employ the form (L + R)/2 may function incorrectly when the sum of L and R exceeds the machine word size, although the individual variables themselves remain valid.
Some programming languages such as Lisp
Lisp programming language
Lisp 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...
, Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
, Perl
Perl
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
, Haskell
Haskell (programming language)
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. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
and Ruby
Ruby (programming language)
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 first 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 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 arithmeticArithmetic logic unit
In 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. Even if the computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
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 1620
The 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...
, IBM 1401
IBM 1401
The IBM 1401 was a variable wordlength decimal computer that was announced by IBM on October 5, 1959. The first member of the highly successful IBM 1400 series, it was aimed at replacing electromechanical unit record equipment for processing data stored on punched cards...
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
Fixed-point arithmetic
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...
format, or in a floating-point format as a significand
Significand
The significand is part of a floating-point number, consisting of its significant digits. Depending on the interpretation of the exponent, the significand may represent 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, 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
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
divided out, 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 complexity
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
for large N.
The simplest algorithms are for addition
Addition
Addition is a mathematical operation that represents combining collections of objects together into a larger collection. 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....
and subtraction
Subtraction
In arithmetic, subtraction is one of the four basic binary 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 notation
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
).
Comparison
Comparison (computer programming)
In computer programming, comparison of two data items is effected by the comparison operators typically written as:Some programming languages make a syntactical distinction between the "equals" of assignment and the "equals" of 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 O(N), but usually it will go much faster.
For multiplication
Multiplication
Multiplication 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) require
operations, but multiplication algorithmMultiplication algorithm
A 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 algorithm, based on fast Fourier transformFast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...
s, and there are also algorithms with slightly worse complexity but with sometimes superior real-world performance for smaller N.
For division
Division (mathematics)
right|thumb|200px|20 \div 4=5In mathematics, especially in elementary arithmetic, division is an arithmetic operation.Specifically, if c times b equals a, written:c \times b = a\,...
, see: Division (digital)
Division (digital)
Several algorithms exist to perform division in digital designs. These algorithms fall into two main categories: slow division and fast division. Slow division algorithms produce one digit of the final quotient per iteration. Examples of slow division include restoring, non-performing restoring,...
.
For a list of algorithms along with complexity estimates, see: Computational complexity of mathematical operations
Computational complexity of mathematical operations
The following tables list the running time of various algorithms for common mathematical operations.Here, complexity refers to the time complexity of performing computations on a multitape Turing machine...
For examples in x86-assembly, see: External links.
Pre-set precision
In some languages such as REXXREXX
REXX is an interpreted programming language that was developed at IBM. It is a structured high-level programming language that was designed to be both easy to learn and easy to read...
the precision of all calculations must be set before doing a calculation. Other languages, such as Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
and Ruby
Ruby (programming language)
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 first developed and designed by Yukihiro "Matz" Matsumoto...
extend the precision automatically to prevent overflow.
Example
The calculation of factorialFactorial
In 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 can easily produce very large numbers. This is not a problem for their usage in many formulae (such as Taylor series
Taylor series
In mathematics, a Taylor series is a representation of a function as an infinite sum of terms that are calculated from the values of the function's derivatives at a single point....
) 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
Stirling's approximation
In mathematics, Stirling's approximation is an approximation for large factorials. It is named after James Stirling.The formula as typically used in applications is\ln n! = n\ln n - n +O\...
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 (see the table below). Even floating-point approximations can exceed the maximum representable floating-point value.
It may help to recast the calculations in terms of the logarithm
Logarithm
The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...
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 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 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 we decided to build the representation in a space-padded text variable and then print that. The first few results 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!
We could try to use the available arithmetic of the computer more efficiently. 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 architectures, 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 architectures provide a "carry flag
Carry flag
In computer processors the carry flag is a single bit in a system status register used to indicate when an arithmetic carry or borrow has been generated out of the most significant ALU bit position...
" 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)² + 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 702IBM 702
The IBM 702 was IBM's response to the UNIVAC—the first mainframe computer using magnetic tapes. Because these machines had less computational power than the IBM 701 and ERA 1103, which were favored for scientific computing, the 702 was aimed at business computing.The system used electrostatic...
(a vacuum tube
Vacuum tube
In electronics, a vacuum tube, electron tube , or thermionic valve , reduced to simply "tube" or "valve" in everyday parlance, is a device that relies on the flow of electric current through a vacuum...
machine) of the mid 1950s, 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 Maclisp
Maclisp
MACLISP 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 system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
s offered bignum facilities as a collection of string functions in the one case and in the EXEC 2
EXEC 2
EXEC 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 REXX
REXX
REXX is an interpreted programming language that was developed at IBM. It is a structured high-level programming language that was designed to be both easy to learn and easy to read...
languages in the other.
An early widespread implementation was available via the IBM 1620
IBM 1620
The 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 table
Lookup table
In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
s) 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 sixty thousand digits, however Fortran
Fortran
Fortran 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.
Stand-alone application software
Software that supports arbitrary precision computations:- bcBc programming languagebc, for bench calculator, is "an arbitrary precision calculator language" with syntax similar to the C programming language. bc is typically used as either a mathematical scripting language or as an interactive mathematical shell....
an arbitrary-precision math program that comes standard on most *nixUnix-likeA 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.- dc: the POSIX desk calculator
- Calc C-style arbitrary precision calculator (LGPL2)
- Maxima (software): a computer algebra systemComputer 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:...
whose "bignum" integers are directly inherited from its implementation language Common LispCommon LispCommon Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
. In addition, it supports arbitrary-precision floating-point numbers, bigfloats. - Maple, MathematicaMathematicaMathematica 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 GMPGNU Multi-Precision LibraryThe GNU Multiple Precision Arithmetic 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. - MatlabMATLABMATLAB is a numerical computing environment and fourth-generation programming language. Developed by MathWorks, MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages,...
with Multiprecision Computing Toolbox. - ND1, a JavaScript and RPL programmable calculator for iPhoneIPhoneThe iPhone is a line of Internet and multimedia-enabled smartphones marketed by Apple Inc. The first iPhone was unveiled by Steve Jobs, then CEO of Apple, on January 9, 2007, and released on June 29, 2007...
- PARI/GPPARI/GPPARI/GP is a computer algebra system with the main aim of facilitating number theory computations. It is free software; versions 2.1.0 and higher are distributed under the GNU General Public License...
, an open sourceOpen sourceThe term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...
computer algebra system that supports arbitrary precision. - Sage, an open-source computer algebra systemComputer 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:...
- TTCalc an open source bignum mathematical calculator (TTMath library).
- Virtual Calc 2000: arbitrary-precision and arbitrary-base calculator for Windows sharewareSharewareThe term shareware is a proprietary software that is provided to users without payment on a trial basis and is often limited by any combination of functionality, availability, or convenience. Shareware is often offered as a download from an Internet website or as a compact disc included with a...
- Wcalc an open source calculator (GMP and MPFR libraries)
Browser Plugin
Online tools
Software that supports limited precision computations available through a web browser:- Big Online Calculator: a bignum calculator for floating point numbers (TTMath library).
- Arbitrary Precision Calculator Applet: a bignum calculator implemented using the apfloat library, or the same without an applet: Arbitrary Precision Calculator
Libraries
Arbitrary-precision arithmetic in most computer software is implemented by calling an external libraryLibrary (computer science)
In computer science, a library is a collection of resources used to develop software. These may include pre-written code and subroutines, classes, values or type specifications....
that provides data type
Data type
In computer programming, a data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of...
s and subroutine
Subroutine
In computer science, a subroutine is a portion of code within a larger program that 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 (Rationals
Rational number
In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
) and some can fully represent computable number
Computable number
In 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...
s, though only up to some storage limit. Fundamentally, Turing machines cannot represent all real numbers, as the cardinality of
exceeds the cardinality of .| Package / Library Name | Number Type | Language | License |
|---|---|---|---|
| apfloat | Decimal floats, integers, rationals Rational number In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number... , and complex Complex number A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part... |
Java Java (programming language) 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++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... |
LGPL GNU Lesser General Public License 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 Freeware Freeware Freeware is computer software that is available for use at no cost or for an optional fee, but usually with one or more restricted usage rights. Freeware is in contrast to commercial software, which is typically sold for profit, but might be distributed for a business or commercial purpose in the... |
| BeeCrypt Cryptography Library | Integers | Assembly, C, C++, Java | LGPL |
| ARPREC and MPFUN | Integers, binary floats, complex binary floats | C++ C++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... with C++ C++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... and Fortran Fortran Fortran 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++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... |
Proprietary |
| bbnum library | Integers and floats | Assembler Assembly language An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture... and C++ C++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... |
New BSD |
| phpseclib | Decimal floats | PHP PHP PHP is a general-purpose server-side scripting language originally designed for web development to produce dynamic web pages. For this purpose, PHP code is embedded into the HTML source document and interpreted by a web server with a PHP processor module, which generates the web page document... |
LGPL |
| BCMath Arbitrary Precision Mathematics | Decimal floats | PHP PHP PHP is a general-purpose server-side scripting language originally designed for web development to produce dynamic web pages. For this purpose, PHP code is embedded into the HTML source document and interpreted by a web server with a PHP processor module, which generates the web page document... |
PHP License |
| BigDigits | Naturals | C C (programming language) C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.... |
Freeware Freeware Freeware is computer software that is available for use at no cost or for an optional fee, but usually with one or more restricted usage rights. Freeware is in contrast to commercial software, which is typically sold for profit, but might be distributed for a business or commercial purpose in the... http://www.di-mgt.com.au/bigdigitsCopyright.txt |
| BigFloat | Binary Floats | C++ C++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... |
GPL GNU General Public License The GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project.... |
| BigNum | Binary Integers, Floats (with math functions) | C# / .NET .NET Framework The .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability... |
Freeware Freeware Freeware is computer software that is available for use at no cost or for an optional fee, but usually with one or more restricted usage rights. Freeware is in contrast to commercial software, which is typically sold for profit, but might be distributed for a business or commercial purpose in the... |
| C++ Big Integer Library | Integers | C++ C++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... |
Public domain Public domain Works are in the public domain if the intellectual property rights have expired, if the intellectual property rights are forfeited, or if they are not covered by intellectual property rights at all... |
| CLN, a Class Library for Numbers 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 Rational number In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number... , floats and complex Complex number A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part... |
C C (programming language) C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.... and C++ C++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... |
GPL GNU General Public License The GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project.... |
| Computable Real Numbers | Reals | Common Lisp Common Lisp Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers... |
|
| dbl |
n x 53 bits precision compact & fast floating point numbers (n=2,3,4,5) | C++ template | Proprietary or GPL GNU General Public License The GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project.... |
| IMSL | C C (programming language) C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.... |
Proprietary | |
| decNumber | Decimals | C C (programming language) C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.... |
ICU International Components for Unicode 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 Fortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing... |
|
| GNU Multi-Precision Library GNU Multi-Precision Library The GNU Multiple Precision Arithmetic Library, also known as GMP, is a free library for arbitrary-precision arithmetic, operating on signed integers, rational numbers, and floating point numbers... (and MPFR MPFR GNU 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 ideas from the ANSI/IEEE-754 standard for fixed-precision... ) |
Integers, rationals and floats | C C (programming language) C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.... and C++ with bindings (GMPY,...) |
LGPL GNU Lesser General Public License 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... |
| MPCLI | Integers | C# / .NET .NET Framework The .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability... |
MIT License MIT License The MIT License is a free software license originating at the Massachusetts Institute of Technology . It is a permissive license, meaning that it permits reuse within proprietary software provided all copies of the licensed software include a copy of the MIT License terms... |
| C# Bindings for MPIR (MPIR is a fork of the GNU Multi-Precision Library GNU Multi-Precision Library The GNU Multiple Precision Arithmetic Library, also known as GMP, is a free library for arbitrary-precision arithmetic, operating on signed integers, rational numbers, and floating point numbers... )] |
Integers, rationals and floats | C# / .NET .NET Framework The .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability... |
LGPL GNU Lesser General Public License 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# / .NET .NET Framework The .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability... |
LGPL GNU Lesser General Public License 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... |
| Eiffel Arbitrary Precision Mathematics Library | Integers | Eiffel Eiffel (programming language) Eiffel is an ISO-standardized, object-oriented programming language designed by Bertrand Meyer and Eiffel Software. The design of the language is closely connected with the Eiffel programming method... |
LGPL GNU Lesser General Public License 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++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... and Assembler Assembly language An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture... |
Proprietary |
| IMath | Integers and rationals | C C (programming language) C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.... |
MIT License MIT License The MIT License is a free software license originating at the Massachusetts Institute of Technology . It is a permissive license, meaning that it permits reuse within proprietary software provided all copies of the licensed software include a copy of the MIT License terms... |
| IntX | Integers | C# / .NET .NET Framework The .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability... |
New BSD |
| JScience LargeInteger | Integers | Java Java (programming language) 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... |
|
| libgcrypt Libgcrypt libgcrypt is a cryptographic library developed as a separated module of GnuPG . It can also be used independently of GnuPG, although it requires its error-reporting library.... |
Integers | C C (programming language) C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.... |
LGPL GNU Lesser General Public License 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... |
| libmpdec (and cdecimal) | Decimals | C C (programming language) C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.... , C++ C++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... and Python Python (programming language) Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive... |
Simplified BSD |
| LibTomMath, Git repo | Integers | C C (programming language) C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.... and C++ C++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... |
Public domain Public domain Works are in the public domain if the intellectual property rights have expired, if the intellectual property rights are forfeited, or if they are not covered by intellectual property rights at all... |
| LiDIA | Integers, floats, complex floats and rationals | C C (programming language) C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.... and C++ C++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... |
Free for non-commercial use |
| MAPM | Integers and decimal floats | C C (programming language) C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.... (bindings for C++ C++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... and Lua) |
Freeware Freeware Freeware is computer software that is available for use at no cost or for an optional fee, but usually with one or more restricted usage rights. Freeware is in contrast to commercial software, which is typically sold for profit, but might be distributed for a business or commercial purpose in the... |
| MIRACL MIRACL (software) MIRACL is an arbitrary-precision arithmetic software package developed by Shamus Software. It is often used in encryption and number theory programs. The source code of this library is publicly available and it can be used for free for educational and non-commercial use... |
Integers and rationals | C C (programming language) C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.... and C++ C++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... |
Free for non-commercial use |
| MPI | Integers | C C (programming language) C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.... |
LGPL |
| MPArith | Integers, floats, and rationals | Pascal / Delphi Pascal (programming language) 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 Zlib License The zlib License is a permissive free software license which defines the terms under which the zlib and libpng software libraries can be distributed. It is also used by other free software packages.... |
| mpmath | Floats, complex floats | Python Python (programming language) Python is a general-purpose, high-level programming language whose 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, floats | C C (programming language) C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.... and C++ C++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... |
GPL GNU General Public License The GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project.... |
| bigInteger (and bigRational) | Integers and rationals | C C (programming language) C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.... and Seed7 |
LGPL GNU Lesser General Public License 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... |
| TTMath library | Integers and binary floats | Assembler Assembly language An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture... and C++ C++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... |
New BSD |
| vecLib.framework | Integers | C C (programming language) C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.... |
Proprietary |
| W3b.Sine | Decimal floats | C# / .NET .NET Framework The .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability... |
New BSD |
| Eiffel Arbitrary Precision Mathematics Library (GMP port) | Integers | Eiffel Eiffel (programming language) Eiffel is an ISO-standardized, object-oriented programming language designed by Bertrand Meyer and Eiffel Software. The design of the language is closely connected with the Eiffel programming method... |
LGPL GNU Lesser General Public License 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... |
| BigInt | Integers | JavaScript JavaScript JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles.... |
Public domain Public domain Works are in the public domain if the intellectual property rights have expired, if the intellectual property rights are forfeited, or if they are not covered by intellectual property rights at all... |
| javascript-bignum | Scheme-compatible decimal integers, rationals, and complex | JavaScript JavaScript JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles.... |
MIT License MIT License The MIT License is a free software license originating at the Massachusetts Institute of Technology . It is a permissive license, meaning that it permits reuse within proprietary software provided all copies of the licensed software include a copy of the MIT License terms... |
| MathX | Integers, floats | C++ C++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... |
Boost Software License Boost Software License The Boost Software License is an open-source license used by the Boost C++ Libraries. It is also a popular license for a significant number of other open source C++ projects... |
| ArbitraryPrecisionFloat | floats (Decimals, Integer and Rational are built in) | Smalltalk 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... |
MIT License MIT License The MIT License is a free software license originating at the Massachusetts Institute of Technology . It is a permissive license, meaning that it permits reuse within proprietary software provided all copies of the licensed software include a copy of the MIT License terms... |
| vlint | Integers | C++ C++ C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell... |
BSD license |
| hapint | Integers | JavaScript JavaScript JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles.... |
MIT License MIT License The MIT License is a free software license originating at the Massachusetts Institute of Technology . It is a permissive license, meaning that it permits reuse within proprietary software provided all copies of the licensed software include a copy of the MIT License terms... or GPL GNU General Public License The GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project.... |
Languages
Programming languages that supports arbitrary precision computations, either built-in, or in the standard library of the language:- Common LispCommon LispCommon Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
: The ANSI Common Lisp standard supports arbitrary precision integer, ratio and complex numbers. - C#: System.Numerics.BigInteger (from .NET 4.0)
- ColdFusionColdFusionIn computing, ColdFusion is the name of a commercial rapid application development platform invented by Jeremy and JJ Allaire in 1995. ColdFusion was originally designed to make it easier to connect simple HTML pages to a database, by version 2 it had...
: the built-in PrecisionEvaluate function evaluates one or more string expressions, dynamically, from left to right, using BigDecimal precision arithmetic to calculate the values of arbitrary precision arithmetic expressions. - Erlang: the built-in Integer datatype implements arbitrary-precision arithmetic.
- GoGo (programming language)Go is a compiled, garbage-collected, concurrent programming language developed by Google Inc.The initial design of Go was started in September 2007 by Robert Griesemer, Rob Pike, and Ken Thompson. Go was officially announced in November 2009. In May 2010, Rob Pike publicly stated that Go was being...
: the standard library package big implements arbitrary-precision integers (Int type) and rational numbers (Rat type) - HaskellHaskell (programming language)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. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
: the built-in Integer datatype implements arbitrary-precision arithmetic. - JJ (programming language)The J programming language, developed in the early 1990s by Kenneth E. Iverson and Roger Hui, is a synthesis of APL and the FP and FL function-level languages created by John Backus....
: built-in extended precision - JavaJava (programming language)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.
- Perl: The bignum and bigrat pragmas provide BigNum and BigRational support for Perl.
- PHP: The BC Math module provides arbitrary precision mathemathics.
- Pike: the built-in int type will silently change from machine-native integer to arbitrary precision as soon as the value exceeds the former's capacity.
- PythonPython (programming language)Python is a general-purpose, high-level programming language whose 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. - Racket: Racket's exact numbers are of arbitrary precision. For instance, (expt 10 100) produces the expected (large) result. Exact numbers also include rationals, so (/ 3 4) produces 3/4.
- REXXREXXREXX is an interpreted programming language that was developed at IBM. It is a structured high-level programming language that was designed to be both easy to learn and easy to read...
: programming language (including Open Object Rexx and NetRexx) - RubyRuby (programming language)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 first 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: Class BigInt.
- Seed7: bigInteger and bigRational.
- SmalltalkSmalltalkSmalltalk 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 SqueakSqueakThe Squeak programming language is a Smalltalk implementation. It is object-oriented, class-based and reflective.It was derived directly from Smalltalk-80 by a group at Apple Computer that included some of the original Smalltalk-80 developers...
, Smalltalk/X, GNU SmalltalkGNU 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 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.) - Standard MLStandard MLStandard ML is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers.SML is a modern descendant of the ML...
: The optional built-in IntInf structure implements the INTEGER signature and supports arbitrary-precision integers.
External links
- Chapter 9.3 of The Art of Assembly by Randall HydeRandall HydeRandall Hyde is best known as the author of , a popular book on assembly language programming. He created the Lisa assembler in the late 1970s and developed the High Level Assembly language....
discusses multiprecision arithmetic, with examples in x86-assembly. - Rosetta Code task Arbitrary-precision integers Case studies in the style in which over 47 programming languages compute the value of 5**4**3**2 using arbitrary precision arithmetic.