Arbitrary-precision arithmetic

Integer arithmetic in which storage grows with the number of numerical digits needed, instead of imposing a fixed word size. It allows exact addition, multiplication, and exponentiation on large integers, subject to available memory; operation costs grow with operand length.

Store an integer in a nonempty array of numeral digits, with the least significant digit first and a fixed radix $b\ge 2$. Normalized digits satisfy $0\le a_i<b$. High-order zeros do not change the value. Adding digit arrays coefficientwise or multiplying them by discrete convolution gives the correct value before normalization, because these operations add or multiply the corresponding powers of the radix. Exact temporary arithmetic, or a radix and accumulator size chosen to prevent integer overflow, is required.

When the radix is $10^k$, print the highest nonzero normalized digit without leading zeros, then every lower digit as exactly $k$ decimal characters. Internal zero blocks must be retained. With base $1000$, the low-first digits $[4,0,12]$ print as 12 followed by 000 followed by 004, giving 12000004. An all-zero representation prints a single zero, independent of its allocated length.

Process a digit-array integer representation from low to high positions. The integer division supplies $q=\lfloor a_i/b\rfloor$ and $0\le r<b$. Replacing the current digit by $r$ and adding $q$ to the next position preserves the represented value. Append zero storage when a positive carry leaves the allocated array. The processed prefix remains normalized and the value stays fixed.

This also works with signed temporary digits when the represented value is nonnegative. A negative carry cannot leave the final allocated position: the normalized lower digits represent a value less than that position's next radix power, which could not offset that negative carry. Positive carries eventually stop beyond the value's finite radix expansion. Thus the usual nonnegative-digit algorithm admits this useful extension without interpreting truncated division as floor division.

Arbitrary-precision integer arithmetic performs exact addition, subtraction, multiplication, and integer division using as many machine words as the value requires. A typical representation stores a sign and digits in base $2^w$, with each digit occupying one machine word. Carries propagate between words just as in written decimal arithmetic.

For example, $2^{1000}+1$ can be stored exactly even when a single machine integer has only $64$ bits. The attainable size is limited by memory and execution time, rather than a fixed numeric range. The cost grows with the number of bits, so an arithmetic operation on a large value cannot automatically be counted as constant time.

Big-integer multiplication multiplies arbitrary-precision integers represented by arrays of digits. For $A={\sum }_i{a}_i{B}^i$ and $C={\sum }_j{c}_j{B}^j$, first compute the coefficient sums $s_k={\sum }_{i+j=k}{a}_i{c}_j$, then propagate carries in base $B$. Thus the main step is a convolution followed by carry handling.

The school method needs $O(n^2)$ digit multiplications for two $n$-digit inputs. Karatsuba multiplication splits each input into two halves and uses three recursive products instead of four, giving $O(n^{{\log }_{2}3})$ arithmetic work under the usual digit model. For larger inputs, transform-based methods accelerate the convolution. Which method is fastest depends on input size and implementation overhead.

An arbitrary-precision integer stores an integer using a variable number of machine words. Unlike a fixed-width integer, it grows when more binary digits are needed. The sign and a finite sequence of base-$2^w$ digits represent its exact value.

For example, the integer $10^{100}+7$ requires hundreds of bits but no rounding. Arbitrary-precision integer arithmetic operates on these representations; it is distinct from approximate floating-point arithmetic. Memory and computation still impose practical bounds, so arbitrary precision does not mean infinite available storage.