[求助]希望有人出手相助编一个用于两个一元多项式相乘的Karatsuba算法的C程序!
上周,老师给我们出了这道题,由于涉及到调用函数,我不是很在行,没能处理 好调用函数的数组返回问题,所以一直调试不通!下周就要上交了,急!希望高手能帮忙!
Karatsuba算法的思想主要是将乘法转化为加法来计算以减少计算复杂度,具体见附件,里面还附带一个用maple程序。
计算两个一元多项式(高次),希望能先宏定义一个程序所能计算的最高次数,用数组表示多项式,数组的坐标表示多项式的该项次数
最好能适用于整系数多项式和浮点型的多项式(实际上我觉得应该只是定义数组类型不同)
谢谢!
Karatsuba’s 快乘乘法
该算法的技巧性在于通过把多项式剖分,以增加加法次数为代价减少了乘法的次数,反复的使用之后,对提高效率的作用是很明显的。
f,g
输出:f、g
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程序