= Divide-and-conquer product ledger
Splitting two <integers> in <positional notation> gives $x=aq+b$ and $y=cq+d$, where $q=B^m$ shifts a block by $m$ <numeral digits> in fixed <radix> $B\geq2$. The <distributive property> gives
$$
xy=acq^2+(ad+bc)q+bd.
$$
Computing $ac,ad,bc,bd$ separately needs four block <multiplications>. Merely halving the operands therefore gives an ideal <recurrence relation> $F(n)=4F(n/2)+O(n)$, still with quadratic <time complexity>. The <Karatsuba three-product identity> instead computes $ac$, $bd$ and $(a+b)(c+d)$, recovering the middle <coefficient> by two <subtractions>. The MIT notes present precisely this four-product versus three-product distinction.<6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff/Lecture 11: Numerics I>[6.006 Introduction to Algorithms, Fall 2011, Lecture 11: Numerics I, printed pp. 4–5, High Precision Multiplication and Karatsuba's Method]{ref}
For an original small example, multiply $47$ by $63$. Set $B=q=10$, $a=4$, $b=7$, $c=6$, $d=3$. Four separate block products would give $ac=24$, $ad=12$, $bc=42$, $bd=21$. The three-product calculation is
$$
\begin{aligned}
u&=ac=24,&v&=bd=21,&w&=(a+b)(c+d)=11\cdot9=99,\\
h&=w-u-v=99-24-21=54,\\
47\cdot63&=100u+10h+v=2400+540+21=2961.
\end{aligned}
$$
The crucial reuse is that $u$ and $v$ supply the outer <coefficients> and also remove the unwanted terms from $w$. There is no need to compute $ad$ and $bc$ separately. Expanding $w=ac+ad+bc+bd$ proves the identity. <Induction> extends it to <Karatsuba multiplication> once each smaller block product is correct and <Karatsuba recursion termination> supplies decreasing sizes and complete <base cases>.
\Image[/divide-and-conquer-four-versus-three-products.png]
{title=Four block products or three: the exact ledger for $47\cdot63$}
{description=The left ledger computes both cross products separately. The right ledger reuses $ac=24$ and $bd=21$ to recover their sum as $99-24-21=54$. Both reconstructions yield $2961$. Counts refer to block <multiplication> calls at this split; the extra <numeral digit> in $4+7=11$ prevents interpreting all three as single-digit products.}
The operation model matters. Let $n$ count <numeral digits> in fixed <radix> $B$, and count single-digit <multiplication>, <addition>, <subtraction> and copying as constant-cost operations. The nonrecursive work on size-$n$ operands is $O(n)$: it includes forming sums, positional shifts and <Karatsuba carry handling>. Treating an arbitrarily large <integer> <multiplication> as one operation would hide the very saving being studied. The coefficients $24,54,21$ above must be shifted and added; concatenating them does not give $2961$.
In the ideal equal-half model, <Karatsuba multiplication> has $K(n)=3K(n/2)+O(n)$. At depth $j$ its additional work is at most a constant times $n(3/2)^j$, and its leaf count is $3^k=n^{\log_2 3}$ for $n=2^k$. A <geometric series> gives $K(n)=O(n^{\log_2 3})$, where $\log_2 3\approx1.585$. Four recursive products would instead give $4^k=n^2$ leaves. Saving one block product repeatedly changes the exponent, even though the combination requires extra <addition> and <subtraction>.
For the literal sum-based version, each operand sum can occupy one extra <numeral digit>. Its worst-case upper <recurrence relation> is $K(n)\leq3K(\lceil n/2\rceil+1)+Cn$ for a nondecreasing cost envelope, above a fixed <base case> threshold of at least three digits. <Karatsuba digit-operation cost> proves that this extra digit preserves the exponent; <Karatsuba operand splitting> handles odd lengths and leading zero padding. For signed <integers>, apply the nonnegative procedure to their <absolute values> and restore the sign. The small ledger establishes an exact identity, while <Karatsuba practical crossover> explains why it alone cannot predict a speedup for two-digit operands.
Back to article page
