Karatsuba算法、Karatsuba乘法、卡拉楚巴乘法、卡拉楚巴算法(俄语:Алгоритм Карацубы),是一种快速乘法算法,由1960年阿纳托利·阿列克谢耶维奇·卡拉楚巴(英语:Anatoly_Karatsuba)提出并于1962年发表。它将两个位数字相乘所需的一位数乘法次数减少到了至多(如果是2的乘方,则正好为)。因此它比要次个位数乘法的经典算法要快。例如,对于两个1024位的数相乘(),卡拉楚巴算法需要次个位数乘法,而经典算法需要次。Toom–Cook算法是此算法更快速的泛型。对于充分大的,Schönhage-Strassen算法甚至更快,算法的时间复杂度为。
值得一提的是,卡拉楚巴算法是第一个比小学二次乘法算法渐进快速的算法。
卡拉楚巴算法主要是用于两个大数的乘法,极大提高了运算效率,相较于普通乘法降低了复杂度,并在其中运用了递归的思想。基本的原理和做法是将位数很多的两个大数和分成位数较少的数,每个数都是原来和位数的一半。这样处理之后,简化为做三次乘法,并附带少量的加法操作和移位操作。
要计算12345和6789的乘积:
对只有三个数进行运算的乘法结果:
将三部分结果相加并相应地移位:
注意:中间第三次乘法运算的输入域小于前两次乘法的两倍,其输出域小于前两次乘法的四倍,并且基数为1000的进位是根据前两次乘法计算的,在计算这两个减法时必须考虑。
热门信息
阅读 (154)
1 如何红喜事选日子,这些方法非常重要阅读 (142)
2 鼠年生人运势怎么样好不好呀女孩 鼠年生人运势怎么样好不好呀女阅读 (131)
3 2024年属狗人的运势 可能财运并不理想阅读 (130)
4 微诗词文学社201112期《原创精选》诗词作品阅读 (113)
5 八字免费测算,解开你命运的谜团!