Anatoly Karatsuba coauthored Multiplication of many-digital numbers by automatic computers by A. Karatsuba and Yu. Ofman. Karatsuba multiplication replaces four half-size products by three, using an algebraic rearrangement to recover the middle term. The resulting recurrence relation gives the exponent instead of two in the usual digit-cost model. This is an early example of changing an algorithm's growth rate through an identity.[ref]
Multiplication of many-digital numbers by automatic computers by A. Karatsuba and Yu. Ofman. Theorem 2 and proof, pp. 293–294
Portrait of Anatoly Karatsuba
. AliceNovak. CC BY-SA 3.0, via Wikimedia Commons. Source. Articles by others on the same topic
Anatoly Karatsuba is a Russian mathematician and computer scientist best known for his contributions to the fields of number theory and algorithm design. He is particularly famous for developing the Karatsuba algorithm in 1960, which is an efficient algorithm for multiplying large integers.