Lesson plan
Karatsuba algorithm
The Karatsuba algorithm is a fast multiplication algorithm for integers. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. It is a divide-and-conquer algorithm that reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers and, by repeating this reduction, to at most n^{\log_23}\approx n^{1.58} single-digit multiplications. It is therefore asymptotically faster than the traditional algorithm, which performs n^2 single-digit products. The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm. The Toom–Cook algorithm (1963) is a faster generalization of Karatsuba's method, and the Schönhage–Strassen algorithm (1971) is even faster, for sufficiently large n.
Article summary
The Karatsuba algorithm is a fast multiplication algorithm for integers. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. It is a divide-and-conquer algorithm that reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers and, by repeating this reduction, to at most n^{\log_23}\approx n^{1.58} single-digit multiplications. It is therefore asymptotically faster than the traditional algorithm, which performs n^2 single-digit products. The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm. The Toom–Cook algorithm (1963) is a faster generalization of Karatsuba's method, and the Schönhage–Strassen algorithm (1971) is even faster, for sufficiently large n.
Key claims
- publication date: 1962 — source: Wikipedia, revision 1374658838, retrieved 2026-10-20 · confidence 0.95
- publication date: 1962 — source: Wikipedia, revision 1374658838, retrieved 2026-10-20 · confidence 0.95
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- The record states that the publication date is "1962". What evidence would count against this claim?
- The record states that the publication date is "1962". What evidence would count against this claim?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
- Wikipedia, “Karatsuba algorithm”, revision 1374658838, retrieved 2026-10-20 https://en.wikipedia.org/w/index.php?oldid=1374658838
Key claims and bibliography are generated from the same tracked claims and sources as the article page.