This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Arbitrary-precision arithmetic" – news ·newspapers ·books ·scholar ·JSTOR(July 2007) (Learn how and when to remove this message)

This article needs editing tocomply with Wikipedia'sManual of Style. In particular, it has problems withMOS:FORMULA - avoid mixing<math>...</math> and{{math}} in the same expression. Please helpimprove the content.(July 2025) (Learn how and when to remove this message)

Incomputer science,arbitrary-precision arithmetic, also calledbignum arithmetic,multiple-precision arithmetic, or sometimesinfinite-precision arithmetic, indicates thatcalculations are performed on numbers whosedigits ofprecision are potentially limited only by the availablememory of the host system. This contrasts with the fasterfixed-precision arithmetic found in mostarithmetic logic unit (ALU) hardware, which typically offers between 8 and 64bits of precision.

Several modernprogramming languages have built-in support for bignums,^[1][2][3][4] and others have libraries available for arbitrary-precisioninteger andfloating-point math. Rather than storing values as a fixed number of bits related to the size of theprocessor register, these implementations typically use variable-lengtharrays of digits.

Arbitrary precision is used in applications where the speed ofarithmetic is not a limiting factor, or whereprecise results with very large numbers are required. It should not be confused with thesymbolic computation provided by manycomputer algebra systems, which represent numbers by expressions such asπ·sin(2), and can thusrepresent anycomputable number with infinite precision.

A common application ispublic-key cryptography, whose algorithms commonly employ arithmetic with integers having hundreds of digits.^[5][6] Another is in situations where artificial limits andoverflows would be inappropriate. It is also useful for checking the results of fixed-precision calculations, and for determining optimal or near-optimal values for coefficients needed in formulae, for example the$\sqrt{\frac{1}{3}}$ that appears inGaussian integration.^[7]

Arbitrary precision arithmetic is also used to compute fundamentalmathematical constants such asπ to millions or more digits and to analyze the properties of the digit strings^[8] or more generally to investigate the precise behaviour of functions such as theRiemann zeta function where certain questions are difficult to explore via analytical methods. Another example is in renderingfractal images with an extremely high magnification, such as those found in theMandelbrot set.

Arbitrary-precision arithmetic can also be used to avoidoverflow, which is an inherent limitation of fixed-precision arithmetic. Similar to an automobile'sodometer display which may change from 99999 to 00000, a fixed-precision integer may exhibitwraparound if numbers grow too large to represent at the fixed level of precision. Some processors can instead deal with overflow bysaturation, 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 anexception if an arithmetic result exceeds the available precision. Where necessary, the exception can be caught and recovered from—for instance, the operation could be restarted in software using arbitrary-precision arithmetic.

In many cases, the task or the programmer can guarantee that the integer values in a specific application will not grow large enough to cause an overflow. Such guarantees may be based on pragmatic limits: a school attendance program may have a task limit of 4,000 students. A programmer may design the computation so that intermediate results stay within specified precision boundaries.

Some programming languages such asLisp,Python,Perl,Haskell,Ruby andRaku use, or have an option to use, arbitrary-precision numbers forall integer arithmetic. This enables integers to grow to any size limited only by the available memory of the system. Although this reduces performance, it eliminates the concern of incorrect results (or exceptions) due to simple overflow. It also makes it possible to almost guarantee that arithmetic results will be the same on all machines, regardless of any particular machine'sword size. The exclusive use of arbitrary-precision numbers in a programming language also simplifies the language, becausea number is a number and there is no need for multiple types to represent different levels of precision.

Arbitrary-precision arithmetic is considerably slower than arithmetic using numbers that fit entirely within processor registers, since the latter are usually implemented inhardware arithmetic whereas the former must be implemented in software. Even if thecomputer lacks hardware for certain operations (such as integer division, or all floating-point operations) and software is provided instead, it will use number sizes closely related to the available hardware registers: one or two words only. There are exceptions, as certainvariable word length machines of the 1950s and 1960s, notably theIBM 1620,IBM 1401 and theHoneywell 200 series, could manipulate numbers bound only by available storage, with an extra bit that delimited the value.

Numbers can be stored in afixed-point format, or in afloating-point format as asignificand 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 thenumerator and for thedenominator. But even with thegreatest common divisor divided out, arithmetic with rational numbers can become unwieldy very quickly: 1/99 − 1/100 = 1/9900, and if 1/101 is then added, the result is 10001/999900.

The size of arbitrary-precision numbers is limited in practice by the total storage available, and computation time.

Numerousalgorithms have been developed to efficiently perform arithmetic operations on numbers stored with arbitrary precision. In particular, supposing thatN digits are employed, algorithms have been designed to minimize the asymptoticcomplexity for largeN.

The simplest algorithms are foraddition andsubtraction, where one simply adds or subtracts the digits in sequence, carrying as necessary, which yields anO(N) algorithm (seebig O notation).

Comparison is also very simple. Compare the high-order digits (or machine words) until a difference is found. Comparing the rest of the digits/words is not necessary. The worst case is${\displaystyle \mathrm{\Theta }}$(N), but it may complete much faster with operands of similar magnitude.

Formultiplication, the most straightforward algorithms used for multiplying numbers by hand (as taught in primary school) require${\displaystyle \mathrm{\Theta }}$(N²) operations, butmultiplication algorithms that achieveO(N log(N) log(log(N))) complexity have been devised, such as theSchönhage–Strassen algorithm, based onfast Fourier transforms, and there are also algorithms with slightly worse complexity but with sometimes superior real-world performance for smallerN. TheKaratsuba multiplication is such an algorithm.

Fordivision, seedivision algorithm.

For a list of algorithms along with complexity estimates, seecomputational complexity of mathematical operations.

For examples inx86 assembly, seeexternal links.

In some languages such asREXX andooRexx, the precision of all calculations must be set before doing a calculation. Other languages, such asPython andRuby, extend the precision automatically to prevent overflow.

The calculation offactorials can easily produce very large numbers. This is not a problem for their usage in many formulas (such asTaylor series) because they appear along with other terms, so that—given careful attention to the order of evaluation—intermediate calculation values are not troublesome. If approximate values of factorial numbers are desired,Stirling's approximation gives good results using floating-point arithmetic. The largest representable value for a fixed-size integer variable may be exceeded even for relatively small arguments as shown in the table below. Even floating-point numbers are soon outranged, so it may help to recast the calculations in terms of thelogarithm of the number.

But if exact values for large factorials are desired, then special software is required, as in thepseudocode that follows, which implements the classic algorithm to calculate 1, 1×2, 1×2×3, 1×2×3×4, etc. the successive factorial numbers.

constants:  Limit = 1000% Sufficient digits.  Base = 10% The base of the simulated arithmetic.  FactorialLimit = 365% Target number to solve, 365!  tdigit: Array[0:9] of character = ["0","1","2","3","4","5","6","7","8","9"]variables:  digit: Array[1:Limit] of 0..9% The big number.  carry, d: Integer% Assistants during multiplication.  last: Integer% Index into the big number's digits.  text: Array[1:Limit] of character% Scratchpad for the output.digit[*] := 0% Clear the whole array.last := 1% The big number starts as a single-digit,digit[1] := 1% its only digit is 1.for n := 1to FactorialLimit:% Step through producing 1!, 2!, 3!, 4!, etc.  carry := 0% Start a multiply by n.for i := 1to last:% Step along every digit.    d := digit[i] * n + carry% Multiply a single digit.    digit[i] := dmod Base% Keep the low-order digit of the result.    carry := ddiv Base% Carry over to the next digit.while carry > 0:% Store the remaining carry in the big number.if last >= Limit: error("overflow")    last := last + 1% One more digit.    digit[last] := carrymod Base    carry := carrydiv Base% Strip the last digit off the carry.  text[*] := " "% Now prepare the output.for i := 1to last:% Translate from binary to text.    text[Limit - i + 1] := tdigit[digit[i]]% Reversing the order.print text[Limit - last + 1:Limit], " = ", n, "!"

With the example in view, a number of details can be discussed. The most important is the choice of the representation of the big number. In this case, only integer values are required for digits, so an array of fixed-width integers is adequate. It is convenient to have successive elements of the array represent higher powers of the base.

The second most important decision is in the choice of the base of arithmetic, here ten. There are many considerations. The scratchpad variabled must be able to hold the result of a single-digit multiplyplus the carry from the prior digit's multiply. In base ten, a sixteen-bit integer is certainly adequate as it allows up to 32767. However, this example cheats, in that the value ofn is not itself limited to a single digit. This has the consequence that the method will fail forn > 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 ofcarry 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 arraydigit, but they would appear with the highest-order digit last (so that 123 would appear as "321"). The whole array could be printed in reverse order, but that would present the number with leading zeroes ("00000...000123") which may not be appreciated, so this implementation builds the representation in a space-padded text variable and then prints that. The first few results (with spacing every fifth digit and annotation added here) are:

This implementation could make more effective use of the computer's built in arithmetic. A simple escalation would be to use base 100 (with corresponding changes to the translation process for output), or, with sufficiently wide computer variables (such as 32-bit integers) we could use larger bases, such as 10,000. Working in a power-of-2 base closer to the computer's built-in integer operations offers advantages, although conversion to a decimal base for output becomes more difficult. On typical modern computers, additions and multiplications take constant time independent of the values of the operands (so long as the operands fit in single machine words), so there are large gains in packing as much of a bignumber as possible into each element of the digit array. The computer may also offer facilities for splitting a product into a digit and carry without requiring the two operations ofmod anddiv as in the example, and nearly all arithmetic units provide acarry 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 faster than the result of the compilation of a high-level language, which does not provide direct access to such facilities but instead maps the high-level statements to its model of the target machine using an optimizing compiler.

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 (blocki, digitj) wherei andj 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.

IBM's first business computer, theIBM 702 (avacuum-tube machine) of the mid-1950s, implemented integer arithmeticentirely in hardware on digit strings of any length from 1 to 511 digits. The earliest widespread software implementation of arbitrary-precision arithmetic was probably that inMaclisp. Later, around 1980, theoperating systemsVAX/VMS andVM/CMS offered bignum facilities as a collection ofstringfunctions in the one case and in the languagesEXEC 2 andREXX in the other.

An early widespread implementation was available via theIBM 1620 of 1959–1970. The 1620 was a decimal-digit machine which used discrete transistors, yet it had hardware (that usedlookup tables) to perform integer arithmetic on digit strings of a length that could be from two to whatever memory was available. For floating-point arithmetic, the mantissa was restricted to a hundred digits or fewer, and the exponent was restricted to two digits only. The largest memory supplied offered 60 000 digits, howeverFortran compilers for the 1620 settled on fixed sizes such as 10, though it could be specified on a control card if the default was not satisfactory.

Arbitrary-precision arithmetic in most computer software is implemented by calling an externallibrary that providesdata types andsubroutines 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 storefloating 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 representcomputable numbers, though only up to some storage limit. Fundamentally,Turing machines cannot represent allreal numbers, as thecardinality of${\displaystyle \mathbb{R}}$ exceeds the cardinality of${\displaystyle \mathbb{Z}}$.

• Fürer's algorithm
• Karatsuba algorithm
• Mixed-precision arithmetic
• Schönhage–Strassen algorithm
• Toom–Cook multiplication
• Little Endian Base 128

• Knuth, Donald (2008).Seminumerical Algorithms.The Art of Computer Programming. Vol. 2 (3rd ed.). Addison-Wesley.ISBN 978-0-201-89684-8., Section 4.3.1: The Classical Algorithms
• Derick Wood (1984).Paradigms and Programming with Pascal. Computer Science Press.ISBN 0-914894-45-5.
• Richard Crandall, Carl Pomerance (2005).Prime Numbers. Springer-Verlag.ISBN 9780387252827., Chapter 9: Fast Algorithms for Large-Integer Arithmetic

• Chapter 9.3 ofThe Art of Assembly byRandall Hyde discusses multiprecision arithmetic, with examples inx86-assembly.
• Rosetta Code taskArbitrary-precision integers Case studies in the style in which over 95 programming languages compute the value of 5**4**3**2 using arbitrary precision arithmetic.

• Computer arithmetic
• Computer arithmetic algorithms

• CS1 French-language sources (fr)
• Articles with short description
• Short description matches Wikidata
• Articles needing additional references from July 2007
• All articles needing additional references
• Wikipedia articles with style issues from July 2025
• All articles with style issues