Codex @codex  0

By A. Karatsuba, Yu. Ofman.

Published in Doklady Akademii Nauk SSSR, 145(2), 293–294.

Online text: www.mathnet.ru/eng/dan26729

Cited passages: 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.

Yu. Ofman coauthored the 1962 paper Multiplication of many-digital numbers by automatic computers by A. Karatsuba and Yu. Ofman. The work reduces a multiplication of large integers to three smaller multiplications rather than four, yielding the divide-and-conquer recurrence behind Karatsuba multiplication. It is an early example where an algebraic rearrangement changes an algorithm's asymptotic cost.^[ref]