Editing Arbitrary-precision arithmetic (section)

==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 [[Arithmetic logic unit|hardware arithmetic]] whereas the former must be implemented in software.  Even if the [[computer]] lacks hardware for certain operations (such as integer division, or all floating-point operations) and software is provided instead, it will use number sizes closely related to the available hardware registers: one or two words only.    There are exceptions, as certain ''[[variable word length machine|variable word length]]'' machines of the 1950s and 1960s, notably the [[IBM 1620]], [[IBM 1401]] and the [[Honeywell 200]] series, could manipulate numbers bound only by available storage, with an extra bit that delimited the value.

Numbers can be stored in a [[fixed-point arithmetic|fixed-point]] format, or in a [[floating-point]] format as a [[significand]] multiplied by an arbitrary exponent.  However, since division almost immediately introduces infinitely repeating sequences of digits (such as 4/7 in decimal, or 1/10 in binary), should this possibility arise then either the representation would be truncated at some satisfactory size or else rational numbers would be used: a large integer for the [[numerator]] and for the [[denominator]]. But even with the [[greatest common divisor]] divided out, arithmetic with rational numbers can become unwieldy very quickly: 1/99 − 1/100 = 1/9900, and if 1/101 is then added, the result is 10001/999900.

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

Numerous [[algorithms]] have been developed to efficiently perform arithmetic operations on numbers stored with arbitrary precision.  In particular, supposing that {{math|''N''}} digits are employed, algorithms have been designed to minimize the asymptotic [[Computational complexity theory|complexity]] for large {{math|''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 {{math|O(''N'')}} algorithm (see [[big O notation]]).

[[Comparison (computer programming)|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 {{math|<math>\Theta</math>(''N'')}}, but it may complete much faster with operands of similar magnitude.

For [[multiplication]], the most straightforward algorithms used for multiplying numbers by hand (as taught in primary school) require {{math|<math>\Theta</math>(''N''<sup>2</sup>)}} operations, but [[multiplication algorithm]]s that achieve {{math|O(''N''&nbsp;log(''N'')&nbsp;log(log(''N'')))}} 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 {{math|''N''}}. The [[Karatsuba algorithm|Karatsuba]] multiplication is such an algorithm.

For [[Division (mathematics)|division]], see [[division algorithm]].

For a list of algorithms along with complexity estimates, see [[computational complexity of mathematical operations]].

For examples in [[x86]] assembly, see [[#External links|external links]].