标题:[求助]希望有人出手相助编一个用于两个一元多项式相乘的Karatsuba算法的C程 ...
取消只看楼主
niceview
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2007-7-1
 问题点数:0 回复次数:2 
[求助]希望有人出手相助编一个用于两个一元多项式相乘的Karatsuba算法的C程序!
上周,老师给我们出了这道题,由于涉及到调用函数,我不是很在行,没能处理 好调用函数的数组返回问题,所以一直调试不通!下周就要上交了,急!
希望高手能帮忙!
Karatsuba算法的思想主要是将乘法转化为加法来计算以减少计算复杂度,具体见附件,里面还附带一个用maple程序。
计算两个一元多项式(高次),希望能先宏定义一个程序所能计算的最高次数,用数组表示多项式,数组的坐标表示多项式的该项次数
最好能适用于整系数多项式和浮点型的多项式(实际上我觉得应该只是定义数组类型不同)
谢谢!


Karatsuba’s 快乘乘法

该算法的技巧性在于通过把多项式剖分,以增加加法次数为代价减少了乘法的次数,反复的使用之后,对提高效率的作用是很明显的。
f,g
R[x]中次数均小于n,R为一个交换幺环,n2的方幂

输出:fg

Step1 n =1 则返回fg

Step2 f=F1*[x^(n/2)]+F0 g=G1*[x^(n/2)]+G0

其中F1 F0 G1 G0都是R[x]中次数均小于n/2的多项式

Step3 通过迭代计算 F1G1 F0G0 F1+F0(G0+G1),

Step4返回F1G*[x^n]+(((F1+F0)(G0+G1)- F0G0- F1G1)* [x^(n/2)]+ F0G0

^后面的数字表示次方

附件为该算法的maple程序

ytv6L6Cu.rar (11.55 KB) [求助]希望有人出手相助编一个用于两个一元多项式相乘的Karatsuba算法的C程序!


搜索更多相关主题的帖子: 多项式 Karatsuba 算法 相乘 
2007-07-01 13:54
niceview
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2007-7-1
得分:0 

快来人帮忙啊
救急啊!!!!!!!!!!

2007-07-01 17:20
niceview
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2007-7-1
得分:0 

救急如救火啊

2007-07-01 19:37



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-151784-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.378914 second(s), 9 queries.
Copyright©2004-2025, BCCN.NET, All Rights Reserved