Lab 05 — Big-Integer Arithmetic & Karatsuba

Goal

Implement arbitrary-precision integers from scratch — limb array in base 10^9 — with schoolbook add/sub/mul, then Karatsuba multiplication in O(n^1.585).

Background

A bignum is a little-endian array of “limbs”: fixed-size chunks of the number. Base 10^9 (9 decimal digits per limb) makes string I/O trivial; real libraries use base 2^30 or 2^64.

Schoolbook multiplication is O(n²) limb operations — pencil-and-paper.

Karatsuba (1960): split each operand at x = BASE^m: a = a₁x + a₀, b = b₁x + b₀. The naive product (a₁x+a₀)(b₁x+b₀) needs 4 half-size multiplications; Karatsuba needs 3:

z₂ = a₁b₁
z₀ = a₀b₀
z₁ = (a₁+a₀)(b₁+b₀) − z₂ − z₀
ab = z₂x² + z₁x + z₀

T(n) = 3T(n/2) + O(n) ⇒ O(n^log₂3) ≈ O(n^1.585). First algorithm to beat n² — disproved Kolmogorov’s conjecture that n² was optimal.

The ladder above it: Toom-3 (5 mults of size n/3, O(n^1.465)), Schönhage–Strassen (FFT-based, O(n log n log log n) — see phase-12 lab-07). CPython switches to Karatsuba at 70 limbs (~630 decimal digits); GMP implements the full ladder.

Interview Context

  • LeetCode 43 “Multiply Strings” is a real FAANG question — schoolbook is the expected answer
  • “How does Python multiply huge ints?” — genuine senior-level follow-up
  • Cryptography engineering: bignum is the core primitive (RSA, ECC)
  • Quant: exact arithmetic, fixed-point libraries
  • ICPC / Codeforces: occasional, mostly in C++ where there is no native bigint
  • Standard FAANG: schoolbook yes; Karatsuba coded live almost never

When to Skip This Topic

Skip if any of these are true:

  • You can’t already write schoolbook “Multiply Strings” cleanly in 25 min
  • You aren’t targeting crypto, systems, quant, or competitive roles
  • You’re weak on divide-and-conquer recurrences — fix that first (Master theorem)

Learn schoolbook regardless. The Karatsuba half is optional for most.

Problem Statement

Exact multiplication of huge integers.

Given two non-negative integers as decimal strings of up to 10^5 digits each, output their exact product. The interviewer bans native bigints (Python int, Java BigInteger) — or equivalently asks “implement what Python does internally.”

Constraints

  • Up to 10^5 decimal digits per operand
  • Result exact — floating point disqualified
  • Wall-clock: < 2 sec
  • No native arbitrary-precision types

Clarifying Questions

  1. Inputs as decimal strings? (Yes, up to 10^5 digits each.)
  2. Negative numbers or leading zeros? (Track sign separately; strip leading zeros; “0” is valid.)
  3. Is the native bigint allowed anywhere? (No — that’s the exercise.)
  4. Exact result required? (Yes.)

Examples

Base-100 limbs, schoolbook, 1234 × 5678. Limbs little-endian: a = [34, 12], b = [78, 56].

position 0: 34×78            = 2652
position 1: 34×56 + 12×78    = 1904 + 936 = 2840
position 2: 12×56            = 672
raw [2652, 2840, 672] → carry → [52, 66, 0, 7] → 7006652

Same product via Karatsuba, x = 100: a₁=12, a₀=34, b₁=56, b₀=78.

z₂ = 12×56 = 672
z₀ = 34×78 = 2652
z₁ = (12+34)(56+78) − z₂ − z₀ = 46×134 − 3324 = 2840
672×100² + 2840×100 + 2652 = 7006652

Three multiplications instead of four.

Brute Force

Digit-by-digit schoolbook on the strings: out[i+j] += a[i]*b[j], then carry pass. For n = 10^5 digits: 10^10 digit multiplies — dead.

Brute Force Complexity

  • Time: O(n²) in digits — 10^10 ops
  • Space: O(n)

Optimization Path

  1. Pack 9 decimal digits per limb (base 10^9): 10^5 digits → 11,112 limbs. Schoolbook drops to ~1.2×10^8 limb multiplies — ~81× fewer, still ~1 min in pure Python.
  2. Karatsuba on limbs: 11112^1.585 ≈ 2.6×10^6 ops — sub-second.
  3. Cutoff: below ~32 limbs schoolbook wins (recursion overhead); fall back.
  4. Beyond scope here: Toom-3, then FFT/NTT (phase-12 lab-07) past ~10^4 limbs.

Final Expected Approach

BASE = 10**9
BASE_DIGITS = 9
CUTOFF = 32

def from_str(s):
    limbs = [int(s[max(0, i - BASE_DIGITS):i]) for i in range(len(s), 0, -BASE_DIGITS)]
    while len(limbs) > 1 and limbs[-1] == 0:
        limbs.pop()
    return limbs

def to_str(limbs):
    return str(limbs[-1]) + "".join(str(x).zfill(BASE_DIGITS) for x in reversed(limbs[:-1]))

def normalize(limbs):
    carry = 0
    for i in range(len(limbs)):
        carry, limbs[i] = divmod(limbs[i] + carry, BASE)
    while carry:
        carry, low = divmod(carry, BASE)
        limbs.append(low)
    while len(limbs) > 1 and limbs[-1] == 0:
        limbs.pop()
    return limbs

def add(a, b):
    n = max(len(a), len(b))
    out = [(a[i] if i < len(a) else 0) + (b[i] if i < len(b) else 0) for i in range(n)]
    return normalize(out)

def sub(a, b):
    out = a[:]
    borrow = 0
    for i in range(len(out)):
        out[i] -= borrow + (b[i] if i < len(b) else 0)
        borrow = 1 if out[i] < 0 else 0
        if borrow:
            out[i] += BASE
    while len(out) > 1 and out[-1] == 0:
        out.pop()
    return out

def school_mul(a, b):
    out = [0] * (len(a) + len(b))
    for i, ai in enumerate(a):
        if ai == 0:
            continue
        carry = 0
        for j, bj in enumerate(b):
            carry, out[i + j] = divmod(out[i + j] + ai * bj + carry, BASE)
        out[i + len(b)] += carry
    return normalize(out)

def karatsuba(a, b):
    if min(len(a), len(b)) <= CUTOFF:
        return school_mul(a, b)
    m = max(len(a), len(b)) // 2
    a0, a1 = a[:m], a[m:] or [0]
    b0, b1 = b[:m], b[m:] or [0]
    z0 = karatsuba(a0, b0)
    z2 = karatsuba(a1, b1)
    z1 = sub(sub(karatsuba(add(a0, a1), add(b0, b1)), z2), z0)
    out = [0] * (len(a) + len(b) + 1)
    for i, v in enumerate(z0):
        out[i] += v
    for i, v in enumerate(z1):
        out[i + m] += v
    for i, v in enumerate(z2):
        out[i + 2 * m] += v
    return normalize(out)

def multiply(s1, s2):
    return to_str(karatsuba(from_str(s1), from_str(s2)))

Data Structures

  • Little-endian list of int limbs, invariant 0 ≤ limb < 10^9, no leading-zero limbs
  • Value = Σ limbs[i] × BASE^i

Correctness Argument

  • Identity: expanding (a₁x+a₀)(b₁x+b₀) gives a₁b₁x² + (a₁b₀+a₀b₁)x + a₀b₀, and (a₁+a₀)(b₁+b₀) − a₁b₁ − a₀b₀ = a₁b₀ + a₀b₁. Exact, no approximation.
  • Normalize preserves value: carrying moves BASE units one limb up; Σ limbs[i]·BASE^i is invariant.
  • Induction: base case schoolbook is correct; recursive case combines three correct sub-products via the identity.
  • Splitting at the low m limbs is exactly a = a₁·BASE^m + a₀.

Complexity

  • Schoolbook: O(n²) — 1.2×10^8 limb mults at n = 11,112 limbs
  • Karatsuba: O(n^log₂3) ≈ O(n^1.585) — ~2.6×10^6 at the same n
  • Space: O(n log n) across recursion in this naive-allocation version; O(n) achievable in-place

Implementation Requirements

  • Little-endian limbs; split takes the LOW half from index 0
  • normalize() after every raw add/mul; sub() assumes a ≥ b (true for z₁ by construction)
  • Cutoff to schoolbook near 32 limbs — pure Karatsuba to length 1 is slower than schoolbook
  • from_str chunks 9 digits from the right; to_str zero-pads all limbs except the most significant
  • Handle unequal lengths and “0”

Tests

  • “1234” × “5678” = “7006652” (both paths)
  • x × “0” = “0”, x × “1” = x
  • Stress: 10^4 random pairs up to 200 digits vs Python native int; assert equal
  • karatsuba vs school_mul agreement at lengths straddling the cutoff (31, 32, 33, 65 limbs)
  • Two 10^5-digit random numbers in < 2 sec
  • Highly unbalanced lengths: 10^5 digits × 3 digits

Follow-up Questions

  • Why base 10^9 and not 2^30? → 10^9 makes decimal I/O O(n) (9 chars per limb); binary bases force an O(n²)-ish radix conversion. 2^30 gives cheaper carries (shifts/masks) and slightly more headroom. Both keep limb products < 2^63. Libraries pick binary and pay at I/O; contest code picks 10^9.
  • When does Karatsuba actually beat schoolbook? → Only past a cutoff — extra adds and allocations dominate small sizes. Tune empirically: ~32 limbs here, 70 digits in CPython, ~10–30 64-bit limbs in GMP. Below cutoff, always fall back.
  • How is division done? → Schoolbook long division is Knuth Algorithm D (TAOCP vol 2): normalize so the top divisor limb ≥ BASE/2, estimate each quotient limb from the top 2–3 limbs, correct at most twice. For huge operands: Newton–Raphson on the reciprocal (xₖ₊₁ = xₖ(2 − d·xₖ)) reuses fast multiplication, so division costs O(M(n)).
  • The full multiplication ladder? → Schoolbook → Karatsuba (~2×10^3 bits) → Toom-3 (~10^4 bits) → Schönhage–Strassen FFT (~10^5–10^6 bits). Crossovers are machine-dependent; GMP tunes per-CPU at build time.
  • How do Python and GMP really do it? → CPython: 30-bit digits, schoolbook below 70 digits, Karatsuba above, nothing faster (multiplying two 10^7-digit ints is visibly slow). GMP: whole ladder plus assembly inner loops — the reason gmpy2 beats native int by 10×+ at scale.

Product Extension

  • Crypto libraries: 2048–4096-bit modmul is the hot loop of RSA/DH
  • Exact decimal money types (java.math.BigDecimal is limb arithmetic underneath)
  • Computer algebra systems, π-computation records (y-cruncher)
  • Blockchain clients: 256-bit fixed-width words — same carry discipline, no recursion

Language/Runtime Follow-ups

  • Python: native int already does all this; the lab is “reimplement without it.” divmod keeps carry code branch-free.
  • C/C++: base 10^9 in uint64_t — one product ~10^18 fits, but accumulating several overflows; carry every inner iteration or drop to base 10^4.
  • Java: BigInteger switches to Karatsuba at 80 ints (2560 bits), Toom-3 at 240.
  • JavaScript: number is a double — 2^53 ceiling forces base ≤ 10^7 for safe products; native BigInt (V8) uses Karatsuba-class algorithms.

Common Bugs

  1. Split from the wrong end: limbs are little-endian — a[:m] is the LOW part. Splitting the high part into z₀ scrambles everything.
  2. Missing final carry: schoolbook inner loop must flush carry into out[i + len(b)].
  3. Leading-zero limbs kept: breaks length-based cutoff logic and comparisons; trim in normalize.
  4. z₁ underflow in C: (a₁+a₀)(b₁+b₀) limbs reach 2·BASE−2 before carrying; subtract with signed intermediates or carry first.
  5. String chunking from the left: from_str must cut 9-digit chunks from the RIGHT; left-chunking corrupts all but exact-multiple lengths.
  6. to_str drops interior zeros: every non-top limb must be zfilled to 9 chars — [52, 66, 0, 7] is 7006652, not 76652.
  7. Unbalanced operands: m from the longer operand can make the shorter one’s high half empty — guard with or [0].

Debugging Strategy

  • Oracle: compare against Python native int on thousands of random cases — the single highest-value test
  • Bisect: verify from_str/to_str round-trip alone, then add, then school_mul, then karatsuba
  • Print limb arrays, not numbers — carry bugs are visible as limbs ≥ BASE
  • Shrink BASE to 10 or 100 to make failing cases hand-checkable

Mastery Criteria

  • Schoolbook “Multiply Strings” in ≤ 25 min, bug-free
  • Full limb bignum with Karatsuba + cutoff in ≤ 60 min
  • Derive the 3-multiplication identity from scratch on a whiteboard
  • Solve T(n) = 3T(n/2) + O(n) and state n^1.585
  • Name the ladder (Karatsuba → Toom-3 → FFT) with rough crossover sizes
  • Explain the base-choice trade-off (10^9 vs 2^30) in under a minute