![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Anatolii_Karatsuba.jpg/640px-Anatolii_Karatsuba.jpg&w=640&q=50)
卡拉楚巴算法
维基百科,自由的 encyclopedia
Karatsuba算法、Karatsuba乘法、卡拉楚巴乘法、卡拉楚巴算法(俄语:Алгоритм Карацубы),是一种快速乘法算法,由1960年阿纳托利·阿列克谢耶维奇·卡拉楚巴(英语:Anatoly_Karatsuba)提出并于1962年发表。[1][2][3]它将两个位数字相乘所需的一位数乘法次数减少到了至多
(如果
是2的乘方,则正好为
)。因此它比要
次个位数乘法的经典算法要快。例如,对于两个1024位的数相乘(
),卡拉楚巴算法需要
次个位数乘法,而经典算法需要
次。Toom–Cook算法是此算法更快速的泛型。对于充分大的
,Schönhage-Strassen演算法甚至更快,算法的时间复杂度为
。
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/0/03/Karatsuba_multiplication.svg/320px-Karatsuba_multiplication.svg.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Anatolii_Karatsuba.jpg/640px-Anatolii_Karatsuba.jpg)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e2/A.A.Karatsuba_on_lecture.jpg/640px-A.A.Karatsuba_on_lecture.jpg)
值得一提的是,卡拉楚巴算法是第一个比小学二次乘法算法渐进快速的算法。