分治算法——Karastsuba算法

时间：2023-03-09 13:04:46
分治算法——Karastsuba算法

分治（Divide and Conquer）算法：问题能够分解为子问题，每一个问题是能够独立的解决的，从子问题的解能够构建原问题。

Divide：中间分、随机分、奇偶分等，将问题分解成独立的子问题

Conquer：子问题的解能够单独解决，从子问题的解构建原问题终于的解

Combine：每一步将子问题产生的解进行合并得到终于的解。合并的复杂度影响终于的算法时间复杂度

Karatsuba算法是在普通乘法算法的基础上进行的提升，使得终于的复杂度从O(n^2)变为了O(n^1.585)。基本思想是将原问题的规模每次减小一般。而且每次解决三个子问题：

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-2-karatsuba-algorithm-for-fast-multiplication/

2.http://en.wikipedia.org/wiki/Karatsuba_algorithm#Pseudo_Code_Implementation


相关文章