一直以来,我们都不曾想过自己习以为常的乘法是否还有其它的做法。

竖式乘法

提出“是否还有其它做法?”这个问题,你可能只能想到竖式,以及重复做加法。你可能会觉得竖式乘法是最好的方法了,但是实际上当乘数非常大的时候,这个运算会变的非常复杂,繁琐。每一位数都需要进行一次乘法计算,那么就会需要次乘法运算,这还没有算接下来的加法!

实际上,关于基本计算方法的研究一直非常活跃。今天介绍一种运用分治思想的乘法算法——Karatsuba乘法,他的发明者当时只是23岁的学生。

Karatsuba算法

Karatsuba算法(未优化)

引用自《算法详解(卷一)——算法基础》

看完后你可能会和我一样一头雾水,这做法简直就是“魔术师突然从自己的帽子里拽出一只兔子一样”。不要着急,这就来解释一下其中的原理。

算法解释

为了方便起见,我们把两个乘数,x和y,都看成是位数为偶数n的数。(对于其它情况,可以在最高位前补0,因此可以用同一算法解决)而x可以表示为2个位的数,即前半部分a和后半部分b。

同样的,y也可以表示成这样:

我们需要计算x与y的乘积,使用基本的多项式运算:

最后我们只需要得出ac,ad,bc,bd的值就大功告成。(什么,你不知道怎么求?真没办法呀,那就告诉你吧QwQ)我们要求四个数的乘积,是为了计算x和y的乘积。这意味着我们可以对这四个数使用同样的算法,对一个问题不断进行分解,直到其中每一个乘积都变成了个位数与个位数乘法这样简单的问题,再一口气解决所有子问题,一步步回到原问题的答案。这就是分而治之的思想。

现在感觉摸到一点门道了吧,但是与Karatsuba算法还是有些出入。这种算法叫做RecIntMult,而Karatsuba算法对它进行了一点优化,这种优化使用的方式仍是一种数学技巧(来自复数乘法)。

优化方法(还能做得更好吗?)

观察上面的多项式。我们真的需要求四个数的乘积吗?实际上我们关心的并不是ad和bc,而是ad+bc。这里,我们先求出ac与bd的值,再求出(a+b)(c+d)的值就能够得到ad+bc,而不用分别计算。这是怎么做到的呢?请看下面的式子。

是不是很巧妙的就把两个乘法变成了一个?从实现的角度来说,它将四个递归1调用节省为三个,在效率上进一步提高。

效率分析

你可能会觉得这种算法要比竖式乘法来得更为麻烦。这里请放下成见,从需要进行的乘法次数角度进行讨论。竖式乘法(长乘法)需要进行次乘法运算,而Karatsuba需要的乘法次数为

假设a,b的位数 n 是 2^k 形式,递归分割了k次,每一次调用都会增加3个子问题,一共有 3^k 个子问题,每个子问题需要1次相乘,即相乘总数为 O(3^k),由于 n = 2^k ,即,k = lg(n),所以时间复杂度为O(3^lg(n)) = O(n^lg(3))

Karatsuba算法实现(C++)

如果读者与我想法一致,即我们在讨论乘法的效率而非存储方式,那不妨看看我的实现。这里假设n为偶数,如有兴趣可以自行实现n为奇数以及两个数位数不同的情况。

#include 
#include
using namespace std;

int Karatsuba(int n,int x,int y)
{
	if (n == 1)
	{
		return x * y;
	}
	else
	{
		int a, b, c, d;
		a = b = x;
		c = d = y;
		int mi = 1;
		for (int i = 0; i < n / 2; i++)
		{
			mi *= 10;
		}
		a /= mi;
		b %= mi;
		c /= mi;
		d %= mi;//拆开
		int ac=Karatsuba(n / 2, a, c);
		//int ad=Karatsuba(n / 2, a, d);
		//int bc=Karatsuba(n / 2, b, c);
		int bd=Karatsuba(n / 2, b, d);
		int p = a + b;
		int q = c + d;
		int pq = Karatsuba(n / 2, p, q);
		int adbc = pq - ac - bd;
		return mi * mi*ac + mi * adbc + bd;
	}
}

int main()
{
	int n, x, y;
	cin >> n >> x >> y;
	int r=Karatsuba(n, x, y);
	cout << r << endl;
	getchar();
	return 0;
}

注释的部分为未改进版。

结语

这里介绍Karatsuba算法的意义并不是强调高效率的乘法算法,而是抛砖引玉,引入分而治之的思想。当一个大问题过于庞大而无法解决时,将其分解成数个子问题,用递归的方式将其解决是一种高明的算法。下次我将会介绍分治的经典算法——归并排序,相信很多读者听过它的大名。希望这些例子能够帮助你将分治变成自己的武器。

Q.E.D

 


1 由于下文就是算法的编程语言实现部分了,这里假定读者具有一定编程基础。递归通俗地说,就是函数调用自身直到触发某个基本条件。

盛夏日落迟 灯火未夜匆匆明