大数相乘实现算法的相关想法 有容老兄要来哟！！！！敢给着个色么
采用分治算法实现 包括两部分的分解
乘数和被乘数 的分解
设 乘数a是由数字集合a={a1,a2,a3...........an} n代表的是a数的位数大于0的正整数 用 a=f(1,n)
设被乘数b是由数字集合b={b1,b2,b3..........bx} x代表的是b数的位数大于0的正整数 b=f(1,x)
被乘数的分解算法
第一次分解 ：
分解结果为：
lift={b1.........bx/2}
right={b(x/2+1).......bx}
用函数表达式 lift=F(1，b/2) ,right=F(x/2+1,x) 表示 n
那么 被乘数 a=lift*10^（x-x/2-1）+right
由乘法规则 (a+b)*c=a*c+b*c的 可以得到
a*b=a* lift*10^（x-x/2-1）+b*right 的表达式 的合并过程
下面怎么推算我就不推了 直接给通项表达式 设b=f(x,y) 则有 right=f(x,(x+y)/2) lift=f((x+y)/2+1,y)
f(x,y)=(lift*10^(y-(x+y)/2-1)+right)*a 合并算法
存在
c 程序的代码段就为
乘数
fenjie(int num,int x, int y)
{
int q
q=(x+y)/2
while(q<y)
{
f1=fenjie (int num,int x,int (x+y)/2)
f2=fenjie(int num,int (x+y)/2+1,int y)
}
合并代码位置
代码完成功能 f(x,y)=(lift*10^(y-(x+y)/2-1)+right)*a 的计算
这个是被乘数
还得对a*bx进行求解 bx代表的是单个位数 再对a进行分解 变成 a的单个数位置上的与bx相乘 的分解合并求解过程,这个过程和上面的 代码是差不多的 嘿嘿
}
呵呵 算法描述完毕
[ 本帖最后由 zhu224039 于 2012-10-3 13:56 编辑 ]
想好了怎么搞，才能更好的搞