= Big-integer multiplication
<Big-integer multiplication> multiplies <arbitrary-precision integers> represented by arrays of digits. For $A=\sum_i a_iB^i$ and $C=\sum_j c_jB^j$, first compute the coefficient sums $s_k=\sum_{i+j=k}a_ic_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.
Back to article page
