找到一个据称是O（n）的卷积算法！

ssikkiss

搞大数的大家有福了！
刚搜到的，还没来得及细看，先发出来在说！ 整数向量卷积的快速算法.pdf (239.62 KB, 下载次数: 16)

2010-6-11 23:52 上传

点击文件名下载附件

ssikkiss

不理解里面的horner方法，搜了下，原来：

秦九韶算法是中国南宋时期的数学家秦九韶提出的一种多项式简化算法。在西方被称作霍纳算法（Horner algorithm或 Horner scheme），是以英国数学家威廉·乔治·霍纳命名的.
　　把一个n次多项式f(x)=a[n]x^n+a[n-1]x^(n-1)+......+a[1]x+a[0]改写成如下形式：
　　f(x)=a[n]x^n+a[n-1]x^(n-1))+......+a[1]x+a[0]
　　=(a[n]x^(n-1)+a[n-1]x^(n-2)+......+a[1])x+a[0]
　　=((a[n]x^(n-2)+a[n-1]x^(n-3)+......+a[2])x+a[1])x+a[0]
　　=......
　　=(......((a[n]x+a[n-1])x+a[n-2])x+......+a[1])x+a[0].
　　求多项式的值时，首先计算最内层括号内一次多项式的值，即
　　v[1]=a[n]x+a[n-1]
　　然后由内向外逐层计算一次多项式的值，即
　　v[2]=v[1]x+a[n-2]
　　v[3]=v[2]x+a[n-3]
　　......
　　v[n]=v[n-1]x+a[0]
　　这样，求n次多项式f(x)的值就转化为求n个一次多项式的值。
　　（注：中括号里的数表示下标）
　　结论：对于一个n次多项式，至多做n次乘法和n次加法。

ssikkiss

一大早起来，我又来思考这个文章，差点让我晕死：
其中未对加法和乘法进行任何定义，所以我按正常的加法和乘法来理解。
其中第2步算出的U（x）和V（x）将是一个大数，而且这步的计算过程因为结果越来越大也不是O（n）的；
U（x）和V（x）是大数，直接导致第三步A=U（x）* V（x）的计算是O（n^2）；

ssikkiss

大概弄懂文意了，作者的向量U和V，因为仅仅是向量，所以作者在第1步给它选了一个进制x，通过第2步把这组向量算成2个大数U（X），和V（X），第3步大数相乘得到A，第4步再求各结果向量。

无心人

高德纳的书里的习题已经对整数卷积给出了个很好的算法
可惜，偶看不懂

ssikkiss

第2，3楼仅是我的主观臆断，请大家不要受此影响而不看原文

gxqcn

粗略地阅读了一下，
它的第四步有（2n-2）次除法，但每次除法实则是O(n)的复杂度，
所以该算法效率将十分低下。

该文发表于《计算数学》1991年2月，如果真有价值，想必现在已到处在引用了。

medie2005

看到中文标题的论文, 就觉得悬了.

mathe

我是看了标题就根本不去看它了