分治算法――Karastsuba算法
來源：程序員人生 發布時間：2014-11-13 08:18:15 閱讀次數：3215次
分治（Divide and Conquer）算法：問題可以分解為子問題，每一個問題是可以獨立的解決的，從子問題的解可以構建原問題。
Divide：中間分、隨機分、奇偶分等，將問題分解成獨立的子問題
Conquer：子問題的解可以單獨解決，從子問題的解構建原問題終究的解
Combine：每步將子問題產生的解進行合并得到終究的解，合并的復雜度影響終究的算法時間復雜度
Karatsuba算法是在普通乘法算法的基礎上進行的提升，使得終究的復雜度從O(n^2)變成了O(n^1.585)，基本思想是將原問題的范圍每次減小1般，并且每次解決3個子問題：
X = Xl*2n/2 + Xr [Xl 左邊n/2位數 Xr 右邊n/2位數]
Y = Yl*2n/2 + Yr [Yl 左邊n/2位數 Yr 右邊n/2位數]
XY = (Xl*2n/2 + Xr)(Yl*2n/2 + Yr)
= 2n XlYl + 2n/2(XlYr + XrYl) + XrYr
XY = 2n XlYl + 2n/2 * [(Xl + Xr)(Yl + Yr) - XlYl - XrYr] + XrYr
XY = 22ceil(n/2) XlYl + 2ceil(n/2) * [(Xl + Xr)(Yl + Yr) - XlYl - XrYr] + XrYr
從
從而得到終究的算法時間復雜度為T(n) = 3T(n/2) + O(n)，得到T(n) = O(n^1.585)。算法的偽代碼以下：
karatsuba(num1, num2)
if (num1 < 10) or (num2 < 10)
return num1*num2
/* calculates the size of the numbers */
m = max(size_base10(num1), size_base10(num2))
m2 = m/2
/* split the digit sequences about the middle */
high1, low1 = split_at(num1, m2)
high2, low2 = split_at(num2, m2)
/* 3 calls made to numbers approximately half the size */
z0 = karatsuba(low1,low2)
z1 = karatsuba((low1+high1),(low2+high2))
z2 = karatsuba(high1,high2)
return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)
下面是使用C++具體實現的進程，如果直接使用整數類型實現，可能會產生溢出，因此使用輸入的字符串表示，實際運算的進程將字符串轉換為數組進行加、減、乘操作。先看終究的算法實現：
string Multiplicate(string x, string y)
{
int len = GetSameSize(x, y);
if (len == 0) return 0;
if (len == 1) return MultiplyString(x, y);
int p = len % 2 == 0 ? len / 2 : len / 2 + 1;
string Xh = x.substr(0, len / 2);
string Yh = y.substr(0, len / 2);
string Xl = x.substr(len / 2);
string Yl = y.substr(len / 2);
string P1 = Multiplicate(Xh, Yh);
string P2 = Multiplicate(Xl, Yl);
string P3 = Multiplicate(AddString(Xh, Xl), AddString(Yh, Yl));
return
AddString(
AddString(
MultiplyPower(P1, 2 * p),
MultiplyPower(MinusString(MinusString(P3, P1), P2), p)
), P2
);
}
上述就是依照偽代碼進行實現，但是使用了字符串的數字運算操作，包括字符串與數組的轉換，數組加、減、乘，具體實現以下：
void StringToArray(string a, int *arr)
{
int n = a.size();
for(int i = 0; i < n; i++)
arr[n - i - 1] = a.at(i) - '0';
}
void ArrayToString(int *arr, int len, string & a)
{
for(int i = 0; i < len; i++)
a += '0' + arr[len - i - 1];
}
string DelPreZero(string a)
{
int zeros = 0;
for (int i = 0; i < a.size(); i++)
if (a.at(i) == '0') zeros++;
else break;
if (zeros == a.size()) return "0";
return a.substr(zeros);
}
void MultiplyArray(int a[], int la, int b[], int lb, int *arr)
{
int i;
for (i = 0; i < la; i++)
for (int j = 0; j < lb; j++)
arr[i + j] += a[i] * b[j];
for (i = 0; i < la + lb - 1; i++)
{
arr[i + 1] += arr[i] / 10;
arr[i] = arr[i] % 10;
}
}
void AddArray(int a[], int la, int b[], int lb, int *arr)
{
int i;
int len = la > lb ? lb : la;
for (i = 0; i < len; i++)
arr[i] += a[i] + b[i];
if (la > lb)
{
for (i = lb; i < la; i++)
arr[i] = a[i];
for (i = 0; i < la; i++)
{
arr[i + 1] += arr[i] / 10;
arr[i] = arr[i] % 10;
}
}
else
{
for (i = la; i < lb; i++)
arr[i] = b[i];
for (i = 0; i < lb; i++)
{
arr[i + 1] += arr[i] / 10;
arr[i] = arr[i] % 10;
}
}
}
void MinusArray(int a[], int la, int b[], int lb, int *arr) //a must be bigger than b
{
int i;
for (i = 0; i < lb; i++)
arr[i] = a[i] - b[i];
for (i = lb; i < la; i++)
arr[i] = a[i];
for (i = 0; i < la - 1; i++)
{
if (arr[i] < 0)
{
arr[i + 1]--;
arr[i] = 10 + arr[i];
}
}
}
string MultiplyString(string a, string b)
{
int m = a.size(), n = b.size();
int *arrA = new int[m];
int *arrB = new int[n];
StringToArray(a, arrA);
StringToArray(b, arrB);
int *arrC = new int[m + n];
for(int i = 0; i < n + m; i++) arrC[i] = 0;
string rst;
MultiplyArray(arrA, m, arrB, n, arrC);
ArrayToString(arrC, m + n, rst);
delete []arrA;
delete []arrB;
delete []arrC;
return DelPreZero(rst);
}
string AddString(string a, string b)
{
int m = a.size(), n = b.size();
int *arrA = new int[m];
int *arrB = new int[n];
StringToArray(a, arrA);
StringToArray(b, arrB);
int i, len = m > n ? m : n;
int *arrC = new int[len + 1];
for(i = 0; i < len + 1; i++) arrC[i] = 0;
AddArray(arrA, m, arrB, n, arrC);
string rst;
ArrayToString(arrC, len + 1, rst);
delete []arrA;
delete []arrB;
delete []arrC;
return DelPreZero(rst);
}
string MultiplyPower(string a, int len)
{
for(int i = 0; i < len; i++)
a += '0';
return DelPreZero(a);
}
string MinusString(string a, string b)
{
int m = a.size(), n = b.size();
int *arrA = new int[m];
int *arrB = new int[n];
StringToArray(a, arrA);
StringToArray(b, arrB);
string rst;
int i, len = m > n ? m : n;
int *arrC = new int[len];
for(i = 0; i < len; i++) arrC[i] = 0;
MinusArray(arrA, m, arrB, n, arrC);
ArrayToString(arrC, len, rst);
delete []arrA;
delete []arrB;
delete []arrC;
return DelPreZero(rst);
}
主要是觸及到字符串與數組的轉換中字符串在數字中是逆序的，進行數組運算時方便，同時對數組間的減法，只支持a 大于b的減法，如果是a 小于b可以用b減去a后再取反便可。還有就是對數組的動態空間申請后，需要及時釋放。
參考：
1.http://www.geeksforgeeks.org/divide-and-conquer-set⑵-karatsuba-algorithm-for-fast-multiplication/
2.http://en.wikipedia.org/wiki/Karatsuba_algorithm#Pseudo_Code_Implementation
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
