| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2389 人关注过本帖
标题:[求助]希望有人出手相助编一个用于两个一元多项式相乘的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
快速回复:[求助]希望有人出手相助编一个用于两个一元多项式相乘的Karatsuba算法 ...
数据加载中...
 
   



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

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