卡拉楚巴算法

Karatsuba算法、Karatsuba乘法、卡拉楚巴乘法、卡拉楚巴算法（俄语：Алгоритм Карацубы），是一种快速乘法算法，由1960年阿纳托利·阿列克谢耶维奇·卡拉楚巴（英语：Anatoly_Karatsuba）提出并于1962年发表。它将两个${\displaystyle n}$位数字相乘所需的一位数乘法次数减少到了至多${\displaystyle 3n^{{\log }_2<!--\; \; -->3}\approx <!--\; \approx \; -->3n^{1.585}}$（如果${\displaystyle n}$是2的乘方，则正好为${\displaystyle n^{{\log }_2<!--\; \; -->3}}$）。因此它比要${\displaystyle n^2}$次个位数乘法的经典算法要快。例如，对于两个1024位的数相乘（${\displaystyle n=1024=2^{10}}$），卡拉楚巴算法需要${\displaystyle 3^{10}=59049}$次个位数乘法，而经典算法需要${\displaystyle (2^{10}{)}^2=1048576}$次。Toom–Cook算法是此算法更快速的泛型。对于充分大的${\displaystyle n(n\gg <!--\; \gg \; -->1)}$，Schönhage-Strassen算法甚至更快，算法的时间复杂度为${\displaystyle O(n\log <!--\; \; -->n\log <!--\; \; -->\log <!--\; \; -->n)}$。

值得一提的是，卡拉楚巴算法是第一个比小学二次乘法算法渐进快速的算法。

卡拉楚巴算法主要是用于两个大数的乘法，极大提高了运算效率，相较于普通乘法降低了复杂度，并在其中运用了递归的思想。基本的原理和做法是将位数很多的两个大数${\displaystyle x}$和${\displaystyle y}$分成位数较少的数，每个数都是原来${\displaystyle x}$和${\displaystyle y}$位数的一半。这样处理之后，简化为做三次乘法，并附带少量的加法操作和移位操作。

要计算12345和6789的乘积：

对只有三个数进行运算的乘法结果：

将三部分结果相加并相应地移位：

注意：中间第三次乘法运算的输入域小于前两次乘法的两倍，其输出域小于前两次乘法的四倍，并且基数为1000的进位是根据前两次乘法计算的，在计算这两个减法时必须考虑。