Anatoly Karatsuba

A Soviet and Russian mathematician (1937–2008) who devised the Karatsuba algorithm for fast multiplication of large numbers.

1 articleLast mentioned

Anatoly Karatsuba was a Soviet and Russian mathematician who worked in analytic number theory and computational mathematics at the Steklov Institute of Mathematics and Moscow State University.

In 1960, while a student at Moscow State University, he devised a divide-and-conquer algorithm that refuted Andrey Kolmogorov's conjecture that multiplying two n-digit numbers requires on the order of n^2 operations. The method, which multiplies in about n^1.585 operations, is known as the Karatsuba algorithm and was the first multiplication algorithm faster than quadratic time.

This entry is based on AIPOST articles and widely known facts. If something is wrong, please send us a correction request.

Articles covering this entry

  • ETH Disproof by OpenAI's AI: What Changes for P vs NP and CryptographyAI News ·

    …gorov conjectured that multiplying two n-bit integers required quadratic time; his 23-year-old student Anatoly Karatsuba found a faster algorithm within a week.

    Read article

Found a mistake or missing an entry?

Wiki entries are based on AIPOST articles and widely known facts. If an entry is wrong, send us a correction request and we will check and fix it. Names from new articles are added to the wiki after the article is published.