来福网

发布于 2023-06-05

Karatsuba算法、Karatsuba乘法、卡拉楚巴乘法、卡拉楚巴算法（俄语：Алгоритм Карацубы），是一种快速乘法算法，由1960年阿纳托利·阿列克谢耶维奇·卡拉楚巴（英语：Anatoly_Karatsuba）提出并于1962年发表。它将两个n{displaystyle n}位数字相乘所需的一位数乘法次数减少到了至多3nlog2⁡3≈3n1.585{disp..