
_START_ARTICLE_
Karatsuba算法
_START_PARAGRAPH_
Karatsuba算法是一种快速相乘算法，它由Anatolii Alexeevitch Karatsuba于1960年提出并于1962年发表。它将两个位数字相乘所需的一位数乘法次数减少到了至多（如果是2的乘方，则正好为）。因此它比要次个位数乘法的经典算法要快。例如，对于两个1024位的数相乘（），Karatsuba算法需要次个位数乘法，而经典算法需要次。Toom–Cook算法是此算法更快速的泛型。对于充分大的,Schönhage–Strassen算法甚至更快，算法的时间复杂度为。_NEWLINE_值得一提的是，Karatsuba算法是第一个比小学二次乘法算法渐进快速的算法。
_START_SECTION_
基本步骤
_START_PARAGRAPH_
Karatsuba的算法主要是用于两个大数的乘法，极大提高了运算效率，相较于普通乘法降低了复杂度，并在其中运用了递归的思想。基本的原理和做法是将位数很多的两个大数和分成位数较少的数，每个数都是原来和位数的一半。这样处理之后，简化为做三次乘法，并附带少量的加法操作和移位操作。
_START_SECTION_
伪代码实现
_START_PARAGRAPH_
procedure karatsuba(num1, num2)_NEWLINE_  if (num1 < 10) or (num2 < 10)_NEWLINE_    return num1*num2_NEWLINE_  /* calculates the size of the numbers */_NEWLINE_  m = max(size_base10(num1), size_base10(num2))_NEWLINE_  m2 = m/2_NEWLINE_  /* split the digit sequences about the middle */_NEWLINE_  high1, low1 = split_at(num1, m2)_NEWLINE_  high2, low2 = split_at(num2, m2)_NEWLINE_  /* 3 calls made to numbers approximately half the size */_NEWLINE_  z0 = karatsuba(low1,low2)_NEWLINE_  z1 = karatsuba((low1+high1),(low2+high2))_NEWLINE_  z2 = karatsuba(high1,high2)_NEWLINE_  return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)
_START_SECTION_
Python代码实现
_START_PARAGRAPH_
#version 2.7.6def karatsuba(num1, num2):_NEWLINE_    if (num1 < 10) or (num2 < 10):_NEWLINE_        return num1*num2_NEWLINE_    num1Str = str(num1)_NEWLINE_    num2Str = str(num2)_NEWLINE__NEWLINE_    maxLength = max(len(num1Str), len(num2Str))_NEWLINE_    splitPosition = maxLength / 2_NEWLINE_    high1, low1= int(num1Str[:-splitPosition]), int(num1Str[-splitPosition:])_NEWLINE_    high2, low2= int(num2Str[:-splitPosition]), int(num2Str[-splitPosition:])_NEWLINE_    z0 = karatsuba(low1, low2)_NEWLINE_    z1 = karatsuba((low1 + high1), (low2 + high2))_NEWLINE_    z2 = karatsuba(high1, high2)_NEWLINE__NEWLINE_    return (z2*10**(2*splitPosition)) + ((z1-z2-z0)*10**(splitPosition))+z0