Karatsuba Integer Multiplication: Complete Algorithm Guide

Introduction and Core Concepts

Karatsuba integer multiplication is a divide-and-conquer algorithm that multiplies two large integers faster than the classical grade-school method. Discovered by Anatoly Karatsuba in 1960, it was the first algorithm to demonstrate that multiplication could be performed in sub-quadratic time, disproving the long-held assumption that O(n²) was optimal. While the naive approach requires four half-sized multiplications to combine partial products, Karatsuba's insight reduces this to three, yielding a significant asymptotic improvement that becomes dramatic as numbers grow to thousands or millions of digits.

At its core, the algorithm exploits an algebraic identity to trade one multiplication for a few extra additions and subtractions. Since addition is linear time O(n) while multiplication is superlinear, this trade-off is highly profitable. For n-digit numbers, the naive algorithm performs O(n²) single-digit multiplications, whereas Karatsuba achieves approximately O(n^1.585). This difference may seem modest for 4-digit numbers, but for cryptographic keys of 2048 or 4096 bits, or for arbitrary-precision arithmetic in scientific computing, the speedup is transformative.

Understanding Karatsuba is essential for any study of divide-and-conquer algorithms because it perfectly illustrates the paradigm: divide the problem into smaller subproblems, conquer them recursively, and combine the results cleverly. It also serves as a gateway to more advanced multiplication techniques such as Toom-Cook and the Schönhage-Strassen algorithm based on the Fast Fourier Transform (FFT). For students and professionals working with big integers, cryptography, or high-performance computing, mastering Karatsuba provides both practical performance gains and deep theoretical insight into algorithmic optimization.

Why Naive Multiplication Is Inefficient

The standard long multiplication you learned in school multiplies every digit of one number by every digit of the other. For two n-digit numbers, this requires n² single-digit multiplications plus O(n²) additions to sum the shifted partial products. When n = 1000, that is one million digit multiplications. Modern computers can handle this, but when n reaches 100,000 digits — common in computational number theory or Python's arbitrary-precision integers — the quadratic cost becomes prohibitive.

Karatsuba addresses this by observing that not all four sub-products are independent. By computing a clever linear combination of the halves, we can infer the middle term without a fourth multiplication. This reduction from four to three recursive multiplications is the entire source of the asymptotic gain, and it compounds at each level of recursion.

Key Terminology

Throughout this guide, we will use n to denote the number of digits or bits in the input. We split each number x and y into high and low halves: x = x1 * B^m + x0 and y = y1 * B^m + y0, where B is the base (10 for decimal, 2^32 or 10^9 for computer implementations) and m = n/2. The terms x0, y0 are the low halves and x1, y1 are the high halves. The product z0 = x0*y0, z2 = x1*y1, and z1 = (x1+x0)*(y1+y0) - z2 - z0 are the three recursive products that enable reconstruction of the final result.

How It Works

The mechanism of Karatsuba integer multiplication can be understood through simple algebra. Let x and y be two n-digit numbers in base B. We choose m = ceil(n/2) and decompose them as described above. A naive divide-and-conquer approach would compute x*y as (x1*B^m + x0)*(y1*B^m + y0) = x1*y1*B^(2m) + (x1*y0 + x0*y1)*B^m + x0*y0. This requires four multiplications: x1*y1, x1*y0, x0*y1, and x0*y0.

Karatsuba's trick is to compute only three products. First, compute z0 = x0*y0 and z2 = x1*y1 directly via recursion. Then compute z1' = (x1 + x0)*(y1 + y0). Expanding z1' gives x1*y1 + x1*y0 + x0*y1 + x0*y0 = z2 + (x1*y0 + x0*y1) + z0. Therefore, the middle coefficient we actually need, x1*y0 + x0*y1, equals z1' - z2 - z0. We obtain it with just one multiplication instead of two, at the cost of a few additions and subtractions.

Once z0, z1 = z1' - z2 - z0, and z2 are known, the final product is assembled as result = z2*B^(2m) + z1*B^m + z0. The operations B^(2m) and B^m are not multiplications at all — in base B they are simply digit shifts, equivalent to appending zeros or, in binary, left shifts. Thus the only expensive operations are the three recursive multiplications.

Recursive Decomposition Tree

Each recursive call splits its inputs again until a base case is reached, typically when numbers are small enough that native hardware multiplication is faster. This creates a ternary recursion tree rather than a quaternary one. At level 0 we have 1 problem of size n, at level 1 we have 3 problems of size n/2, at level 2 we have 9 problems of size n/4, and so on. After log2(n) levels, we reach single-digit problems. The total work is dominated by the leaves, but there are far fewer leaves than in the naive approach (3^log2(n) = n^log2(3) ≈ n^1.585 vs 4^log2(n) = n²).

Handling Odd Lengths and Different Sizes

In practice, numbers rarely have exactly power-of-two lengths. If n is odd, we can pad with a leading zero or split unevenly, for example m = n//2, so that the low part has m digits and the high part has n-m digits. The algorithm works correctly regardless of exact split, though balanced splits yield optimal performance. When x and y have different lengths, we can pad the shorter one or split based on max(len(x), len(y)). Modern implementations often use a threshold to switch to naive multiplication for small sizes to avoid recursion overhead.

Implementation

Implementing Karatsuba correctly requires careful handling of base, splitting, recursion, and base cases. Below are several Python implementations progressing from educational clarity to production-ready optimization. All examples use base 10 for readability, but production code typically uses base 10^9 or 2^30 to align with machine words and reduce the number of digits.

def naive_multiply(x, y):
    """Grade-school O(n^2) multiplication for comparison."""
    # Python's built-in big integers use Karatsuba internally,
    # but we implement naive for benchmarking
    if x < 10 or y < 10:
        return x * y
    # For illustration only - not efficient
    return x * y  # placeholder for digit-by-digit logic

def karatsuba_basic(x, y):
    """Simplest recursive Karatsuba - clear but not optimized."""
    # Base case: single digit multiplication is trivial
    if x < 10 or y < 10:
        return x * y
    
    # Calculate the size of the numbers
    n = max(len(str(x)), len(str(y)))
    m = n // 2
    
    # Split the digit sequences about the middle
    # x = x1 * 10^m + x0, y = y1 * 10^m + y0
    x1, x0 = divmod(x, 10**m)
    y1, y0 = divmod(y, 10**m)
    
    # 3 recursive calls instead of 4
    z0 = karatsuba_basic(x0, y0)
    z2 = karatsuba_basic(x1, y1)
    z1 = karatsuba_basic(x1 + x0, y1 + y0) - z2 - z0
    
    # Combine results with shifts (multiplying by powers of 10)
    return z2 * 10**(2*m) + z1 * 10**m + z0

def karatsuba_optimized(x, y, threshold=1000):
    """
    Optimized Karatsuba with cutoff to naive multiplication.
    Uses string length for splitting and avoids recomputing powers.
    """
    # Base case: use native multiplication for small numbers
    # Threshold prevents recursion overhead from dominating
    if x < threshold or y < threshold:
        return x * y
    
    # Use string conversion to get digit count without log10 overhead
    # For binary implementations, use bit_length()
    n = max(len(str(x)), len(str(y)))
    m = n // 2
    
    # More efficient split using pow10 cache
    pow10_m = 10 ** m
    pow10_2m = pow10_m * pow10_m
    
    x1, x0 = divmod(x, pow10_m)
    y1, y0 = divmod(y, pow10_m)
    
    # Recursive steps - note that (x1+x0) and (y1+y0) may have m+1 digits
    z0 = karatsuba_optimized(x0, y0, threshold)
    z2 = karatsuba_optimized(x1, y1, threshold)
    # This addition can cause carry, but recursion handles it
    z1 = karatsuba_optimized(x1 + x0, y1 + y0, threshold) - z2 - z0
    
    return z2 * pow10_2m + z1 * pow10_m + z0

def karatsuba_binary(x, y):
    """
    Binary Karatsuba using bit operations - closer to real-world implementation.
    Splits based on bit length, uses shifts instead of base-10 powers.
    """
    if x < 10 or y < 10:
        return x * y
    
    # n is max bit length
    n = max(x.bit_length(), y.bit_length())
    m = n // 2
    
    # Split using bit shifts: x = x1 * 2^m + x0
    # Mask for low m bits: (1 << m) - 1
    mask = (1 << m) - 1
    x0 = x & mask
    x1 = x >> m
    y0 = y & mask
    y1 = y >> m
    
    z0 = karatsuba_binary(x0, y0)
    z2 = karatsuba_binary(x1, y1)
    z1 = karatsuba_binary(x1 + x0, y1 + y0) - z2 - z0
    
    # Combine with shifts: z2 * 2^(2m) + z1 * 2^m + z0
    return (z2 << (2*m)) + (z1 << m) + z0

def karatsuba_iterative_wrapper(x, y):
    """
    Wrapper that handles signs, zero, and uneven lengths robustly.
    This is the function you would expose in a library.
    """
    # Handle zero and sign
    if x == 0 or y == 0:
        return 0
    sign = -1 if (x < 0) ^ (y < 0) else 1
    x, y = abs(x), abs(y)
    
    # Ensure x is the larger for consistent splitting (optional)
    if x < y:
        x, y = y, x
    
    result = karatsuba_optimized(x, y)
    return sign * result

# Example usage and simple benchmark
if __name__ == "__main__":
    a = 123456789123456789123456789
    b = 987654321987654321987654321
    # Python's built-in uses Karatsuba + FFT, so we compare logic
    expected = a * b
    result = karatsuba_iterative_wrapper(a, b)
    print(f"Correct: {result == expected}")
    print(f"Result: {result}")
    
    # Test odd digit handling
    x, y = 12345, 6789  # different lengths, odd n
    print(f"Odd test: {karatsuba_iterative_wrapper(x, y)} == {x*y}")

def karatsuba_with_cutoff_analysis(x, y, cutoff=4):
    """
    Educational version that counts operations and shows recursion depth.
    cutoff = number of digits below which to use naive multiplication.
    """
    def helper(a, b, depth=0):
        indent = "  " * depth
        # Base case: naive multiplication
        if len(str(a)) <= cutoff or len(str(b)) <= cutoff:
            # In real code, this would be O(n^2) digit multiplication
            return a * b
        
        n = max(len(str(a)), len(str(b)))
        m = n // 2
        pow10_m = 10 ** m
        
        a1, a0 = divmod(a, pow10_m)
        b1, b0 = divmod(b, pow10_m)
        
        # For debugging, uncomment:
        # print(f"{indent}Split {a} -> {a1} | {a0}, {b} -> {b1} | {b0}")
        
        z0 = helper(a0, b0, depth+1)
        z2 = helper(a1, b1, depth+1)
        z1 = helper(a1 + a0, b1 + b0, depth+1) - z2 - z0
        
        return z2 * 10**(2*m) + z1 * pow10_m + z0
    
    return helper(x, y)

# Demonstrate recursion depth vs naive
# For n=32 digits, Karatsuba depth ~5, naive would need 1024 leaf multiplications
# Karatsuba needs only 3^5 = 243 leaf multiplications

Note the critical detail in the optimized versions: x1 + x0 and y1 + y0 can produce an extra digit due to carry. This does not break correctness but means the recursive call for z1 may operate on inputs of size m+1 rather than m. Some implementations handle this by using max(m, len(str(x1+x0))) for the next split, while others simply recurse and let the next level handle it. Both are correct, but the latter is simpler.

Step-by-Step Example

Let us walk through a concrete example to solidify the mechanism. We will multiply x = 1234 and y = 5678 using base B = 10 and m = 2 (since n = 4 digits, m = n/2 = 2). This splits each number into two 2-digit halves.

First, decompose the inputs. For x = 1234, we have x1 = 12 (high part) and x0 = 34 (low part), so x = 12*100 + 34. For y = 5678, we have y1 = 56 and y0 = 78, so y = 56*100 + 78. We will compute three products: z0 = x0*y0 = 34*78, z2 = x1*y1 = 12*56, and z1' = (x1+x0)*(y1+y0) = (12+34)*(56+78) = 46*134.

Compute each product. If we apply Karatsuba recursively, even these 2-digit products would be split again, but for this walkthrough we will compute them directly to keep the example short. z0 = 34*78 = 2652. z2 = 12*56 = 672. z1' = 46*134 = 6164. Now derive the middle term: z1 = z1' - z2 - z0 = 6164 - 672 - 2652 = 2840. This value equals x1*y0 + x0*y1 = 12*78 + 34*56 = 936 + 1904 = 2840, confirming our trick worked without ever computing those two products separately.

Recombining the Result

Now assemble the final answer using shifts. result = z2*B^(2m) + z1*B^m + z0 = 672*10000 + 2840*100 + 2652. Calculate: 672*10000 = 6,720,000; 2840*100 = 284,000; plus 2652 gives 7,006,652. Verify with direct multiplication: 1234*5678 = 7,006,652. The result matches.

Consider what happened at the next recursion level if we had continued. To compute z0 = 34*78, we would split 34 into 3|4 and 78 into 7|8 with m=1. Then z0_low = 4*8=32, z0_high=3*7=21, z0_mid=(3+4)*(7+8)-21-32=7*15-53=105-53=52. Recombine: 21*100 + 52*10 + 32 = 2100+520+32=2652. This recursive breakdown shows how the algorithm bottoms out at single-digit multiplications.

Tracing Recursion Depth and Work

For our 4-digit example, the recursion tree has depth 2 (4 -> 2 -> 1 digit). At the top level we performed 1 addition to form (x1+x0) and (y1+y0), 3 recursive multiplications, and 2 subtractions plus 2 shifts to combine. At the bottom level, each leaf does a single-digit multiplication. Total leaf multiplications: 3^2 = 9, compared to 4^2 = 16 for naive divide-and-conquer. For larger n, the gap widens exponentially. This walkthrough also highlights why the base case matters: if we recursed down to 1 digit for numbers with thousands of digits, the overhead of Python function calls and string conversions would dominate. Practical implementations stop at 32-64 digits and switch to naive or hardware multiplication.

Complexity Analysis

The time complexity of Karatsuba is derived from its recurrence relation. Let T(n) be the time to multiply two n-digit numbers. The algorithm performs three recursive calls on inputs of size n/2, plus O(n) work for additions, subtractions, and shifts. This gives T(n) = 3*T(n/2) + O(n). Applying the Master Theorem for divide-and-conquer recurrences, we compare n^log_b(a) where a=3, b=2, so n^log2(3) ≈ n^1.585, with f(n)=O(n). Since f(n) = O(n^log2(3) - epsilon) for epsilon ≈ 0.585, we are in Case 1, yielding T(n) = Theta(n^log2(3)).

Space complexity is O(n) for the recursion stack and temporary storage if implemented naively, or O(log n) stack depth plus O(n) auxiliary space for storing intermediate sums. Some in-place implementations can reduce auxiliary space, but the recursion depth itself is logarithmic. The best, average, and worst cases are identical in terms of asymptotic complexity because the algorithm always splits and recurses the same way regardless of input digits; there is no data-dependent early termination.

It is important to distinguish between digit complexity and bit complexity. When analyzing in terms of bits, n is the number of bits, and base B = 2. The same recurrence holds. For decimal digits, the constant factors change but the exponent remains log2(3). The hidden constant in O(n^1.585) includes the cost of additions, which are linear but have a non-trivial coefficient due to carry propagation.

Understanding the Recurrence

To see why T(n) = 3T(n/2)+O(n) solves to O(n^1.585), consider the recursion tree. At level k, there are 3^k nodes each of size n/2^k, and each node does O(n/2^k) work for additions. Total work at level k is 3^k * O(n/2^k) = O(n*(3/2)^k). Summing across log2(n) levels gives a geometric series dominated by the leaves, where work is Theta(3^log2(n)) = Theta(n^log2(3)). This is a classic example where the leaf work dominates the internal node work, unlike mergesort where each level contributes equally.

Practical Crossover Point

Asymptotic analysis hides constant factors. Karatsuba does more additions and has recursion overhead, so for small n, naive multiplication is actually faster. Empirical measurements in Python, Java BigInteger, and GMP show the crossover typically occurs between 32 and 128 digits (or 200-1000 bits), depending on implementation quality and hardware. Below this threshold, the O(n²) algorithm wins due to lower overhead. This is why production libraries use a hybrid approach: if n < threshold, use naive; else use Karatsuba; and for very large n (e.g., > 10,000 digits), switch to Toom-Cook or FFT.

Variations and Optimizations

Several refinements improve Karatsuba's practical performance beyond the textbook version. The most important is the cutoff optimization: rather than recursing to single digits, stop when inputs fall below a tuned threshold and use naive multiplication or built-in hardware multiplication. This reduces recursion depth and avoids the overhead of splitting tiny numbers. The optimal threshold is determined empirically by benchmarking on target hardware and is often exposed as a tunable parameter.

Another optimization is to use a larger base. Instead of base 10, use base 10^9 or 2^30 so that each "digit" fits in a 32-bit word. This reduces n (the number of digits) by a factor of 9 or 9-10, dramatically reducing recursion depth. For example, a 1000-decimal-digit number becomes only 111 base-10^9 digits. Python's long object internally uses base 2^30, and Java's BigInteger uses base 2^32, both for this reason.

Iterative and tail-recursive formulations can reduce stack overhead. While the natural expression is recursive, some implementations use an explicit stack or iterative deepening to avoid Python's recursion limit and function call overhead. Additionally, memoization of powers of B (like 10^m) avoids recomputing large exponents repeatedly.

Toom-Cook Generalization

Karatsuba is the simplest case of the Toom-Cook family. Toom-3 splits each number into three parts and reduces 9 naive multiplications to 5, achieving O(n^1.465). Toom-4 reduces 16 to 7, and so on. Each higher Toom-Cook variant reduces the exponent further but increases the additive overhead and interpolation complexity. Karatsuba (Toom-2) offers the best trade-off for moderate sizes (hundreds to a few thousand digits), while Toom-3 and Toom-4 become beneficial for larger inputs.

Parallel and Cache-Friendly Variants

The three recursive multiplications are independent and can be executed in parallel on multi-core systems. A parallel Karatsuba can achieve near 3x speedup on three cores for large inputs, though load balancing is tricky because the middle product (x1+x0)*(y1+y0) may be slightly larger. Cache optimization involves ensuring that the digit arrays for x0, x1, y0, y1 fit in cache lines and that shifts are implemented as pointer offsets rather than actual digit moves. In languages like C, this is done by passing array slices and offsets instead of copying subarrays.

Handling Negative Numbers and Uneven Splits

Optimized implementations handle sign separately, converting to absolute values and reapplying the sign at the end. For uneven splits, some variants use the technique of splitting at m = floor(n/2) and padding the shorter high part with zeros, while others use a recursive formula that works for any m: if x = x1*B^m + x0, the recombination is still z2*B^(2m) + z1*B^m + z0 even when x1 and y1 have different lengths than x0 and y0. The key is that B^m corresponds to the size of the low part, not necessarily half the total digits.

Real-World Applications

Karatsuba integer multiplication is not merely an academic curiosity; it underpins critical infrastructure wherever large integers arise. In cryptography, RSA key generation and operations involve modular exponentiation with 2048- to 4096-bit integers (600-1200 decimal digits). Each RSA encryption or decryption performs hundreds of large multiplications, and using Karatsuba (and its successors) directly impacts TLS handshake latency, VPN throughput, and blockchain transaction verification. OpenSSL, GnuPG, and Java's JCA all use Karatsuba as part of their big-integer multiplication pipeline.

In computer algebra systems such as Mathematica, Maple, and SageMath, arbitrary-precision arithmetic is fundamental. Multiplying polynomials with large coefficients, computing factorials of large numbers, or evaluating high-precision constants like pi to millions of digits all rely on fast multiplication. Python's built-in int type, which transparently supports arbitrary precision, switched to Karatsuba and later to more advanced algorithms for large ints; without it, operations like 100000! would be impractically slow.

Scientific computing and signal processing also benefit. While floating-point FFT multiplication dominates for extremely large numbers, Karatsuba is often faster for intermediate sizes encountered in intermediate calculations, such as in lattice-based cryptography or error-correcting codes. Databases that store large numeric types (e.g., DECIMAL with high precision) and web servers that handle big integer JSON payloads may also invoke Karatsuba indirectly through their language runtimes.

Where Karatsuba Is Not Used

For small integers that fit in 64 bits, hardware multiplication is O(1) and Karatsuba is never invoked. Web servers handling typical 32-bit request IDs or database primary keys use native CPU instructions. Similarly, for extremely large numbers (millions of digits), FFT-based methods outperform Karatsuba asymptotically and are preferred in libraries like GMP for the largest inputs. Karatsuba occupies the crucial middle ground: too large for hardware, too small for FFT overhead to pay off.

Comparison with Alternatives

Choosing a multiplication algorithm depends on input size, implementation complexity, and constant factors. The naive algorithm is simplest and fastest for small n. Karatsuba improves asymptotically with modest complexity. Toom-Cook variants offer better exponents at the cost of more complex interpolation. FFT-based algorithms achieve near-linear time but have high overhead and are only worthwhile for very large n. Understanding these trade-offs is essential for library designers and for interview discussions about algorithm selection.

A key insight is that no single algorithm dominates all sizes. Modern big-integer libraries implement a cascade: naive for n < threshold1, Karatsuba for threshold1 ≤ n < threshold2, Toom-3 for threshold2 ≤ n < threshold3, and FFT beyond that. Thresholds are tuned per architecture. For example, CPython's longobject.c uses Karatsuba for 70-100 digits and switches to more advanced methods for larger sizes, while GMP has finely tuned thresholds for each CPU.

When to Choose Karatsuba

Choose Karatsuba when you need a simple, proven improvement over naive multiplication for numbers in the hundreds to thousands of digits, and you want to avoid the complexity of Toom-Cook or FFT. It is ideal for educational implementations, interview coding problems, and production systems where input sizes are known to be moderate. If you are writing a general-purpose big-integer library, implement Karatsuba as the first optimization tier and benchmark to find the exact crossover points on your hardware.

Hybrid Strategies in Practice

Real libraries rarely use pure Karatsuba for all sizes. Instead, they implement a function like multiply(a,b) that checks if n < KARATSUBA_THRESHOLD: return naive(a,b); elif n < TOOM_THRESHOLD: return karatsuba(a,b); else: return fft_multiply(a,b). This ensures optimal performance across the entire range. The thresholds are often determined at compile time or even at runtime via autotuning. For interview purposes, mentioning this hybrid approach demonstrates practical engineering awareness beyond theoretical complexity.

Common Mistakes and Best Practices

Implementing Karatsuba correctly is surprisingly error-prone, especially under interview pressure. The most frequent mistake is incorrect handling of the base and exponent when recombining. Using 10**(2*m) when m was computed as n//2 for odd n can misalign digits. For example, if n=5 and m=2, then 10**(2*m)=10000, but the high part actually represents 3 digits, not 2. The safe approach is to compute m = n//2 and use pow10_m = 10**m and pow10_2m = pow10_m * pow10_m, which correctly accounts for the low part size regardless of oddness.

Another common pitfall is forgetting that x1 + x0 and y1 + y0 may overflow by one digit. If x1 and x0 are both m-digit numbers close to 10^m -1, their sum can be m+1 digits. Failing to account for this can cause incorrect splits in the recursive call or, in fixed-width implementations, integer overflow. The recursive call must handle inputs of size m+1 gracefully, which it will if the base case and splitting logic are robust.

Performance mistakes include recursing too deeply, using string conversion inside every recursive call, and not caching powers of 10. Converting integers to strings to compute length is convenient but expensive; using bit_length() for binary or precomputing digit counts is faster. Similarly, computing 10**m repeatedly via exponentiation is wasteful; compute it once per level and pass it down or use shifts.

Best Practices Checklist

• Always handle sign and zero separately before recursion to simplify logic and avoid negative splits.
• Use a threshold to switch to naive multiplication; tune it empirically rather than guessing. Start with 32 digits or 1000 as integer value and benchmark.
• Prefer base 2^30 or 10^9 over base 10 for production code to reduce n and leverage word-sized operations.
• Implement iterative or tail-recursive versions if recursion depth may exceed language limits (Python recursion limit ~1000).
• Test with edge cases: zero, one, powers of 10, numbers with different lengths, odd digit counts, and maximum recursion depth.
• Verify correctness against Python's built-in multiplication for random large numbers in unit tests.
• Document whether your implementation is for decimal strings, Python ints, or digit arrays, as the splitting logic differs.

Debugging Tips

If your Karatsuba returns incorrect results, first test the recombination formula in isolation: compute z0, z1, z2 via naive multiplication and verify that z2*B^(2m) + z1*B^m + z0 equals the expected product. If that passes, the bug is in the recursive logic or splitting. Print the recursion tree for a small example like 12*34 and compare each node's inputs and outputs to manual calculations. Finally, ensure you are not using floating-point division or / instead of integer // and divmod, which can introduce rounding errors for large numbers.

Interview Questions

Question 1: Derive the Time Complexity of Karatsuba

Question: Write the recurrence for Karatsuba and solve it using the Master Theorem. Why does it beat O(n²)?

Answer: The recurrence is T(n) = 3T(n/2) + O(n), where 3 is the number of recursive multiplications, n/2 is the subproblem size, and O(n) is the cost of additions, subtractions, and shifts. By the Master Theorem, a=3, b=2, f(n)=O(n). Compute n^log_b(a) = n^log2(3) ≈ n^1.585. Since f(n) = O(n) = O(n^log2(3) - epsilon) with epsilon ≈0.585, Case 1 applies, so T(n)=Theta(n^log2(3)). It beats O(n²) because 3^log2(n) < 4^log2(n); we do fewer recursive multiplications (3 vs 4), and additions are cheaper than multiplications.

Question 2: Implement Karatsuba and Handle Edge Cases

Question: Implement Karatsuba in Python for arbitrary non-negative integers. How do you handle odd lengths and different-sized inputs?

Answer: Use the implementation shown in the Implementation section with divmod and base 10^m. For odd lengths, compute m = n//2 where n = max(len(str(x)), len(str(y))), so the low part always has m digits and the high part has n-m digits; recombination still uses B^m and B^(2m) based on m. For different sizes, pad the shorter number conceptually by treating missing high digits as zero — divmod naturally handles this because dividing a smaller number by 10^m yields high part 0. Always handle base cases (x < 10 or y < 10) and consider a threshold to avoid excessive recursion.

Question 3: When Would You Not Use Karatsuba?

Question: If Karatsuba is asymptotically faster, why do we still use naive multiplication?

Answer: Due to constant factors and overhead. Karatsuba performs extra additions and has recursion overhead (function calls, splitting, allocating intermediate numbers). For small n (typically < 32-64 digits or < 1000 bits), these overheads exceed the savings from one fewer multiplication. Hardware multiplication for 32/64-bit ints is O(1) and far faster. Therefore production code uses a hybrid: naive below a threshold, Karatsuba above it, and FFT for very large n. The crossover point must be measured empirically.

Question 4: Compare Karatsuba with Toom-Cook and FFT

Question: How does Karatsuba relate to Toom-Cook and FFT-based multiplication? Which would you use for 1,000,000-digit numbers?

Answer: Karatsuba is Toom-2, the simplest Toom-Cook algorithm. Toom-3 splits into 3 parts and does 5 multiplications (O(n^1.465)), Toom-4 does 7 multiplications, etc., each reducing the exponent but increasing interpolation overhead. FFT-based methods like Schönhage-Strassen achieve O(n log n log log n) by using Fourier transforms to convert multiplication to pointwise multiplication. For 1,000,000 digits, FFT would be fastest; Karatsuba's O(n^1.585) would be too slow, and even Toom-Cook would be outperformed by FFT at that scale. The choice depends on n: naive for small, Karatsuba for medium, Toom for large, FFT for huge.

Question 5: Optimize Karatsuba for Production

Question: Your Karatsuba implementation is correct but slow in Python. How would you optimize it?

Answer: Several optimizations: 1) Add a cutoff threshold to use Python's built-in * (which is already optimized in C) for small numbers. 2) Use base 2^30 or 10^9 instead of base 10 to reduce digit count. 3) Avoid string conversion for length; use bit_length() for binary or cache lengths. 4) Cache powers of 10 or use bit shifts (<<) for binary. 5) Use iterative approach or increase recursion limit to avoid recursion overhead. 6) For parallel hardware, execute the three recursive calls concurrently. 7) Profile to find the optimal threshold rather than recursing to single digits. In practice, Python's built-in int already implements Karatsuba in C, so pure Python will always be slower; the optimization is to delegate to it for small sizes.