乘法算法-Karatsuba算法

考虑两个n位整数x和y的乘法。基本的算法是O(n^2)的。以10进制为例,用bigint表示大整数类型,s[1]表示个位,len为位数。

按照小学数学多位数乘法法则,程序如下:

bigint mult(bigint a, bigint b)
{
	bigint c;
	c.len = a.len + b.len ;
	for(int i=1; i <= c.len; i++) c.s[i] = 0;
	for(int i=1; i <= a.len; i++)
		for(int j=1; j <= b.len; j++)
			c.s[i+j-1] += a.s[i]*b.s[j];
	for(int i=1; i<= c.len ; i++)
		{ c.s[i+1] += c.s[i]/10; c.s[i] %= 10; }
}

这个算法实际上是先计算每一位上的原始数,然后从低位往高位调整使得每一位都是0-9。这个算法需要原始数不上溢。对于第k位,满足i + j – 1 = k的数对(i, j)最多有n个,因此原始数最多81n,在时间可以承受的范围之内都不会溢出。

现在考虑分治算法。取m = (n+1)/2,把x写成10^m*a+b的形式,y写成10^m*c+d的形式,则a, b, c, d都是m位整数(如果不足m位,前面可以补0)。

《乘法算法-Karatsuba算法》

递归方程为T(n) = 4T(n/2) + O(n),其中系数4为四次乘法ac, bd, bc, ad,附加代价n为最后一个return语句的两次高精度加法。方程的解为T(n) = O(n^2),和暴力乘法没有区别。

Anatolii Karatsuba在1962年提出一个改进方法(并由Knuth改进):用ac和bd计算bc + ad,即:

bc + ad = ac + bd – (a – b) * (c – d)

这样一来,只需要进行三次递归乘法,即递归方程变为了T(n) = 3T(n/2)+O(n),解为T(n) = O(nlog3) = O(n^1.585),比暴力乘法快。

计算整数乘法的最快算法是基于FFT的,它的时间复杂度为O(n log n)。

    原文作者:jiyanfeng1
    原文地址: https://blog.csdn.net/jiyanfeng1/article/details/8543846
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞