Arbitrary-precision integer arithmetic

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.