大数相乘的算法（instructed by Western University Prof.Schost
发布时间：2020-12-14 03:59:54 所属栏目：大数据 来源：网络整理
导读：一、Karatsuba算法主要应用于两个大数的相乘，原理是将大数分成两段后变成较小的数位，然后做3次乘法，并附带少量的加法操作和移位操作。 现有两个大数，x，y。 首先将x，y分别拆开成为两部分，可得x1，x0，y1，y0。他们的关系如下： x = x1 * 10 m ?+ x0；
|
一、Karatsuba算法主要应用于两个大数的相乘，原理是将大数分成两段后变成较小的数位，然后做3次乘法，并附带少量的加法操作和移位操作。
现有两个大数，x，y。
首先将x，y分别拆开成为两部分，可得x1，x0，y1，y0。他们的关系如下：
x = x1 * 10
m?+ x0；
y = y1 * 10
m?+ y0。其中m为正整数，m < n，且x0，y0 小于 10
m。
那么 xy = (x1 * 10
m?+ x0)(y1 * 10
m?+ y0)
=z2 * 10
2m?+ z1 * 10
m?+ z0，其中：
z2 = x1 * y1；
z1 = x1 * y0 + x0 * y1；
z0 = x0 * y0。
此步骤共需4次乘法，但是由Karatsuba改进以后仅需要3次乘法。因为：
z1 = x1 * y0+ x0 * y1
z1 = (x1 + x0) * (y1 + y0) - x1 * y1 - x0 * y0，
故x0 * y0 便可以由加减法得到。
例子：
设x = 12356，y=6789，令m=3。那么有：
12345 = 12 * 1000 + 345；
6789 = 6 * 1000 + 789。
下面计算：
z2 = 12 * 6 = 72；
z0 = 345 * 789 = 272205；
z1 = (12 + 345) * (6 + 789) - z2 - z0 = 11538。
然后我们按照移位公式（xy = z2 * 10 + z1 * 10 + z0）可得：
xy = 72 * 1000
2?+ 11538 * 1000 + 272205 = 83810205。
算法的复杂度不超过3n
log3?≈ 3n
1.585。
伪代码：
procedure karatsuba(num1,num2)
???
if
(num1 < 10) or (num2 < 10)? ?
???? ???
return
num1*num2??
???
/* calculates the size of the numbers */??
???
m = max(size(num1),size(num2))??
low1,low2 = lower half of num1,num2??
high1,high2 = higher half of num1,num2??
/* 3 calls made to numbers approximately half the size */??
z0 = karatsuba(low1,low2)??
z1 = karatsuba((low1+high1),(low2+high2))??
z2 = karatsuba(high1,high2)??
(z2*10^(m))+(（z1-z2-z0）*10^(m/2))+(z0)
二、 Toom's algorithm 对于以上的F,G F,G中x的最高次数是k-1,H=FG,H中x的最高次数就是2k-2;（k是F,G中因子的项数） Evaluation.
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
