Big Integer Multiplication

Multiplying two $n$-digit numbers is the same problem as multiplying two degree-$n$ polynomials, plus carry propagation.

The ladder

Method	Time	Crossover (limbs)
Schoolbook	$O(n^2)$	< ~30
Karatsuba	$O(n^{1.585})$	30 – 300
Toom-Cook 3/4	$O(n^{1.465})$ / $O(n^{1.404})$	300 – 3000
FFT / NTT	$O(n\log n)$	> ~3000
Schönhage-Strassen	$O(n\log n\log \log n)$	very large
Fürer	$O(n\log n{2}^{O({\log }^{\ast }n)})$	never (galactic)
Harvey-van der Hoeven	$O(n\log n)$	never (galactic)

Every serious library (GMP, Java’s BigInteger, Python’s int) implements the first four with tuned thresholds.

The unifying idea

All of Karatsuba, Toom-Cook and FFT are evaluate → multiply pointwise → interpolate:

Method	Evaluation points
Karatsuba	$0,1,\infty$ (3 points)
Toom-3	$0,1,-1,2,\infty$ (5 points)
Toom-$k$	$2k-1$ small integers
FFT	the $n$ roots of unity

At small sizes, evaluating at a few integers is cheap and interpolation is a fixed formula. At large sizes, roots of unity make both evaluation and interpolation cost $O(n\log n)$ instead of $O(n)$-with-a-huge-constant — which is why FFT eventually wins.

FFT-based multiplication

vector<long long> multiplyBig(const string& s, const string& t) {
    // digits little-endian, base 10 (or pack 3-4 digits per limb)
    vector<long long> a, b;
    for (int i = s.size() - 1; i >= 0; i--) a.push_back(s[i] - '0');
    for (int i = t.size() - 1; i >= 0; i--) b.push_back(t[i] - '0');
 
    vector<long long> c = convolution(a, b);          // FFT or NTT
 
    long long carry = 0;                              // propagate carries
    for (size_t i = 0; i < c.size(); i++) {
        c[i] += carry;
        carry = c[i] / 10;
        c[i] %= 10;
    }
    while (carry) { c.push_back(carry % 10); carry /= 10; }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

Base choice matters. With base $10^k$ and length $n$, the convolution values reach $n\cdot (10^k{)}^2$; double FFT holds about 53 bits, so $n\cdot 10^{2k}<2^{53}$ constrains $k$. For $n=10^6$, $k=3$ is safe and $k=4$ is marginal. NTT has no such limit.

Other big-integer operations

Operation	Method	Cost
Addition, subtraction	schoolbook	$O(n)$
Multiplication	as above	$O(n\log n)$
Division	Newton on the reciprocal	$O(M(n))$
Modulo	division	$O(M(n))$
Square root	Newton	$O(M(n))$
Base conversion	divide and conquer	$O(M(n)\log n)$
GCD	binary GCD, or half-GCD	$O(n^2)$ / $O(M(n)\log n)$
Modular exponentiation	square and multiply + Montgomery	$O(M(n)\log e)$

Division by Newton: compute $1/b$ as a fixed-point reciprocal with $x\leftarrow x(2-bx)$, doubling the correct bits each step, then multiply. Total cost is $O(M(n))$ — the same order as one multiplication.

In competitive programming

Usually you should not need big integers:

Instead	Use
Huge exact counts	the answer modulo a prime
Comparing $ab$ vs $cd$	__int128
$a^b\mathrm{mod}m$	fast exponentiation
Exact factorials	mod p, or Legendre’s formula
Values up to $10^{38}$	__int128
Genuinely arbitrary precision	Python, if the judge allows it

See Big Integer Arithmetic for a minimal hand-rolled implementation.

When it does appear

Problems that genuinely require it: exact Fibonacci or factorial values, cryptography-flavoured tasks, and “print the exact answer” problems with $10^4$-digit outputs. In those, a base-$10^9$ schoolbook implementation is nearly always sufficient — FFT-based multiplication is needed only above a few thousand digits.

See also: Karatsuba · Toom-Cook · Big Integer Arithmetic