卡拉楚巴算法 Karatsuba算法Karatsuba乘法卡拉楚巴乘法卡拉楚巴算法俄語Алгоритм Карацубы是一种快速乘法算法由年阿納托利阿列克謝耶維奇卡拉楚巴英语AnatolyKaratsuba提出并于年发表它将两个 n displaystyle n 位数字相乘所需的一位数乘法次数减少到了至多  n log      n  displaystyle nlog approx n 如果 n displaystyle n 是的乘方则正好为 n log    displaystyle nlog  因此它比要 n  displaystyle n 次个位数乘法的经典算法要快例如对于两个位的数相乘 n      displaystyle n 卡拉楚巴算法需要     displaystyle  次个位数乘法而经典算法需要        displaystyle  次ToomCook算法是此算法更快速的泛型对于充分大的 n  n    displaystyle nngg  SchönhageStrassen演算法甚至更快算法的时间复杂度为 O  n log  n log  log  n  displaystyle Onlog nlog log n  值得一提的是卡拉楚巴算法是第一个比小学二次乘法算法渐进快速的算法