= Karatsuba three-product identity
{c}
{title2=$xy=acB^{2m}+((a+b)(c+d)-ac-bd)B^m+bd$}
Compute exactly three smaller products,
$$
p_2=ac,\qquad p_0=bd,\qquad p_s=(a+b)(c+d).
$$
The <distributive property> gives $p_s=ac+ad+bc+bd$, so the cross coefficient is $h=p_s-p_2-p_0=ad+bc$. Recombine by
$$
xy=p_2q^2+hq+p_0,\qquad q=B^m.
$$
The saving is that $ad$ and $bc$ are never separately multiplied. Multiplying a digit block by $q$ or $q^2$ shifts its position in <positional notation>; it does not require another general <integer> <multiplication>. <Addition> of the shifted results still requires <Karatsuba carry handling>.
\Image[/karatsuba-three-product-dataflow.png]
{title=Three products recover the Karatsuba cross coefficient}
{description=The arrows carry exact <integer> values for the <Karatsuba worked multiplication>. Only the three coloured product boxes require recursive <multiplication>; the lower boxes use <subtraction>, digit shifts and <addition>.}
Back to article page
