卡拉楚巴算法是一种快速乘法算法，它由阿纳托利·阿列克谢耶维奇·卡拉楚巴于1960年提出并于1962年发表。它将两个
n
{\displaystyle n}
位数字相乘所需的一位数乘法次数减少到了至多
3
n
log
2
3
≈
3
n
1.585
{\displaystyle 3n^{\log _{2}3}\approx 3n^{1.585}}
。因此它比要
n
2
{\displaystyle n^{2}}
次个位数乘法的乘法算法算法要快。例如，对于两个1024位的数相乘，卡拉楚巴算法需要
3
10
=
59049
{\displaystyle 3^{10}=59049}
次个位数乘法，而经典算法需要
2
=
1048576
{\displaystyle ^{2}=1048576}
次。图姆-库克算法是此算法更快速的泛型。对于充分大的
n
{\displaystyle n}
，Schönhage-Strassen算法甚至更快，算法的时间复杂度为
O
{\displaystyle O}
。
卡拉楚巴算法是一种快速乘法算法，它由阿纳托利·阿列克谢耶维奇·卡拉楚巴于1960年提出并于1962年发表。它将两个
n
{\displaystyle n}
位数字相乘所需的一位数乘法次数减少到了至多
3
n
log
2
3
≈
3
n
1.585
{\displaystyle 3n^{\log _{2}3}\approx 3n^{1.585}}
。因此它比要
n
2
{\displaystyle n^{2}}
次个位数乘法的乘法算法算法要快。例如，对于两个1024位的数相乘，卡拉楚巴算法需要
3
10
=
59049
{\displaystyle 3^{10}=59049}
次个位数乘法，而经典算法需要
2
=
1048576
{\displaystyle ^{2}=1048576}
次。图姆-库克算法是此算法更快速的泛型。对于充分大的
n
{\displaystyle n}
，Schönhage-Strassen算法甚至更快，算法的时间复杂度为
O
{\displaystyle O}
。
Mini wiki
