主题：求助:大整数乘法 分三段 怎么使它减为5次乘法的?
chenpx
[专家分：110] 发布于 2006-04-08 08:24:00
用分治法求两个n位的大整数u和v的乘积时,将u和v分割为n/3位
的3段.证明可以用5次n/3位整数的乘法求得uv值.设计算法,并
求复杂性.
将u分成u1,u2,u3三段，v分成v1，v2，v3三段
则:u*v可分为:
u1*v1
u3*v3
u1*v2+u2*v1
u1*v3+u2*v2+u3*v1
u2*v3+u3*v2
回复列表 （共6个回复）
沙发
chenpx [专家分：110] 发布于 2006-04-08 12:05:00
有没有会的啊，急~~~，怎么把上面9个乘法改写成只要计算5次乘法就可以了啊。。。。。。
板凳
eagleking0000 [专家分：3330] 发布于 2006-04-08 13:40:00
u1*v1,u1*v2,u1*v3,u2*v2,u2*v3
就这五个你把结果分别存起来,用的时候再调用就行了
3 楼
chenpx [专家分：110] 发布于 2006-04-08 17:56:00
不行啊,用那五个乘法得不出结果.还有以下四个式子求不出来...
u3*v3
u2*v1
u3*v1
u3*v2
那位大大帮帮忙,把它简化一下啊..
4 楼
euc [专家分：4310] 发布于 2006-04-09 08:40:00
因为结果也只要3段，所以高位的不必去理会。
5 楼
boxertony [专家分：23030] 发布于 2006-04-09 22:29:00
见我的blog。
6 楼
chenpx [专家分：110] 发布于 2006-04-10 13:29:00
看了,不过就是得不出结果
经过这几天的学习
终于凑出了结果，呵呵：
五个乘法为:
M1=u1*v1
M2=u3*v3
M3=（u1+u2+u3）*（v1+v2+v3）
M4=（u1-u2+u3）*（v1-v2+v3）
M5=（u1-2*u2+4*u3）*（v1-2v2+4v3）
则：
u1*v1=M1
u3*v3=M2
u1*v2+u2*v1=（2M1-6M2+M3）/6+u1*v1/2-2u3*v3
u1*v3+u2*v2+u3*v1=（M1+M2）/2-u1*v1-u3*v3
u2*v3+u3*v2=（M1+3M2-M3）/6-u1*v1/2+2u3*v3
这样就只用五次乘法了．
我来回复
您所在位置：