 Big-integer multiplication

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.