Karatsuba algorithm
The Karatsuba algorithm is a fast multiplication algorithm. 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 single-digit multiplications. It is therefore asymptotically faster than the traditional algorithm, which performs single-digit products. For example, the traditional algorithm requires (210)2 = 1,048,576 single-digit multiplications to multiply two 1024-digit numbers (n = 1024 = 210), whereas the Karatsuba algorithm requires 310 = 59,049 thus being ~17.758 times faster.
- Comment
- enThe Karatsuba algorithm is a fast multiplication algorithm. 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 single-digit multiplications. It is therefore asymptotically faster than the traditional algorithm, which performs single-digit products. For example, the traditional algorithm requires (210)2 = 1,048,576 single-digit multiplications to multiply two 1024-digit numbers (n = 1024 = 210), whereas the Karatsuba algorithm requires 310 = 59,049 thus being ~17.758 times faster.
- Depiction
- Has abstract
- enThe Karatsuba algorithm is a fast multiplication algorithm. 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 single-digit multiplications. It is therefore asymptotically faster than the traditional algorithm, which performs single-digit products. For example, the traditional algorithm requires (210)2 = 1,048,576 single-digit multiplications to multiply two 1024-digit numbers (n = 1024 = 210), whereas the Karatsuba algorithm requires 310 = 59,049 thus being ~17.758 times faster. 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.
- Is primary topic of
- Karatsuba algorithm
- Label
- enKaratsuba algorithm
- Link from a Wikipage to an external page
- www.cs.pitt.edu/~kirk/cs1501/animations/Karatsuba.html
- cr.yp.to/papers/m3.pdf
- Link from a Wikipage to another Wikipage
- Anatoly Karatsuba
- Andrey Kolmogorov
- Asymptotically optimal
- Asymptotic complexity
- Big O notation
- Big-O notation
- Binary multiplier
- Carry-save adder
- Category:Articles with example pseudocode
- Category:Computer arithmetic algorithms
- Category:Divide-and-conquer algorithms
- Category:Multiplication
- Charles Babbage
- Computational complexity theory
- Computer platform
- Cybernetics
- Divide-and-conquer algorithm
- File:Karatsuba multiplication.svg
- Imaginary unit
- Long multiplication
- Master theorem (analysis of algorithms)
- Moscow State University
- Multiplication algorithm
- Proceedings of the USSR Academy of Sciences
- Radix
- Recurrence relation
- Recursion
- Schönhage–Strassen algorithm
- Time complexity
- Toom–Cook multiplication
- Yuri Petrovich Ofman
- SameAs
- 4oyxr
- Algorisme de Karatsuba
- Algorithme de Karatsuba
- Algoritmo de Karacuba
- Algoritmo de Karatsuba
- Algoritmo de Karatsuba
- Algoritmo di Karatsuba
- Algorytm Karacuby
- Karacubovo násobení
- Karatsuba algorithm
- Karazuba-Algorithmus
- m.0g3ts6
- Q629940
- Алгоритм Карацубы
- Карацубин алгоритам
- Множення Карацуби
- الگوریتم کاراتسوبا
- കരത്സൂബാ അൽഗൊരിതം
- ขั้นตอนวิธีของคาราซูบา
- カラツバ法
- 卡拉楚巴算法
- 카라추바 알고리즘
- Subject
- Category:Articles with example pseudocode
- Category:Computer arithmetic algorithms
- Category:Divide-and-conquer algorithms
- Category:Multiplication
- Thumbnail
- Title
- enKaratsuba Multiplication
- Urlname
- enKaratsubaMultiplication
- WasDerivedFrom
- Karatsuba algorithm?oldid=1113431971&ns=0
- WikiPageLength
- 13620
- Wikipage page ID
- 6395589
- Wikipage revision ID
- 1113431971
- WikiPageUsesTemplate
- Template:MathWorld
- Template:Mvar
- Template:Number-theoretic algorithms
- Template:Reflist
- Template:Short description
