= Karatsuba multiplication
{c}
{wiki}
<Karatsuba multiplication> is a <divide-and-conquer algorithm> for <multiplication> of <integers>. Splitting each operand into two blocks seems to require four smaller products; the <Karatsuba three-product identity> recovers the two cross terms together from just three products. Repeating that saving through <recursion> changes the <time complexity> from quadratic to $O(n^{\log_2 3})$, where $n$ counts digits in a fixed <positional notation>. The exponent is about $1.585$: the benefit comes from the <algorithm>, even though each splitting step needs more <addition> and <subtraction>.
The <Karatsuba worked multiplication> below computes $1234\cdot5678=7{,}006{,}652$ using $12\cdot56$, $34\cdot78$, and $46\cdot134$. The last operand already shows why “half-size” needs care: <Karatsuba carry handling> and <Karatsuba recursion termination> account for the extra digit. <Karatsuba digit-operation cost> states the operation model; <Karatsuba practical crossover> explains why the asymptotic saving alone does not select a useful threshold.
The original 1962 paper presents a <binary numeral system> automaton construction: its Theorem 2 and proof reduce <multiplication> to taking <squares of numbers>, then reduce a larger <square of a number> to three smaller <squares of numbers>. Its footnote explicitly addresses the extra digit in a sum of halves. The sequential <time complexity> analysis below uses a different operation model from that paper's automaton size and depth bounds, including its <Boolean circuit> realization without feedback.<Multiplication of many-digital numbers by automatic computers by A. Karatsuba and Yu. Ofman>[Karatsuba and Ofman, Multiplication of many-digital numbers by automatic computers, original Russian article, 1962, pp. 293–294: Theorem 2, its proof, and the footnote on p. 294]{ref}
Back to article page
