发布时间 : 星期日 文章SoCVista8.快速卷积更新完毕开始阅读995c8066f5335a8102d22076
H?p??h0?h1p?????hN?1pN?1，X?p??x0?x1p?????xL?1pL?1
卷积结果就是S?p??H?p??X?p?的各项系数，即
S?p??s0?s1p?????sN?L?2pN?L?2
中的?s0,s1,???,sN?L?2?。Cook-Toom算法所要做的就是利用拉格朗日插值公式，导出S?p?的符号式。注意，不要犯如下错误，
代码 3
> 直接用多项式相乘，算出S?p?，如上2?2卷积结果，从中是看不出任何用于构造快速卷积计算矩阵的信息的。我们真正需要的是推导出S?p?的中间过程，在例题中可以深刻体会到中间结果的对于构造快速卷积的作用。
因为N?L线性卷积结果为N+L-1个点，所以S?p?是N+L-2阶多项式，根据拉格朗日插值定理，必须给出N+L-1个互不相同的点对??i,Si?方可确定S?p?。Cook-Toom算法的步骤是：
1） 选择L+N-1个不同的实数?0,?1,...,?L?N?2，一般是选择整数，如0,?1,?2,?3等，不同
取值将会导致不同的快速卷积结果。
2） 计算ssi?S??i??H??i??X??i?，因为S?p?目前还是未知的，所以不能直接在
S?p?中带入?i来得到S??i?，而是应该求H??i?和X??i?然后两者相乘，而H?p?和X?p?是已知的；注意“惰性的1”H??i??X??i?形式是至关重要的。 3） 利用拉格朗日插值公式，算出S?p?的符号式。
注：也许步骤2和步骤3应该交换顺序，至少在实现时是这样的，请注意阅读程序，弄明白其中的道理。
说得再多，都比不上看例题明白。接下来以2?3卷积为例，说明如何通过Cook-Toom算法设计快速卷积。
??i??h0?h1和X??i??x1，
“惰性”计算H??i??X??i???h0?h1??x1，“勤劳”计算H??i??X??i??h0?x1?h1?x1。
1
借用maple的术语，惰性指的是不用真正计算，仅列出形式。假设H
按照课本上的设定，设置好N，L和N+L-1个?值（大家也可以试试选择其他不同的?值，看看最后结果相比课本上的结果如何）。
代码 4
> > >
根据N+L-1个不同点对??i,ssi?求出S?p?
代码 5
> > 接下来给出ssi的惰性表示。首先给出H?p?和X?p?，然后在求各个?i处的值（程序中有
。 hhi?H??i?且xxi?X??i?）
代码 6
> > 惰性计算ssi，其中还计算了S?p?最高次项的系数，以便在改进的Cook-Toom算法中使用。
代码 7
> 至此，即可动手写出快速卷积的矩阵形式。
根据提取代码5的S?p?的各项系数，也就是卷积的结果有
ss0???1?11??ss0?ss1?ss2?ss3?36??2?? 11?ss0?ss1?ss2??22???1111??ss0?ss1?ss2?ss3?266??2将上式分解成如下形式，确保不要在左矩阵中只出现整数（想想最大公约数就明白了）。不
得不说这个过程完全是靠观察写出，好在这种分解十分容易！！！
?1?ss0???2ss0??1???11??ss0?ss1?ss2?ss3??2000??1?36???12?2?1??ss1??2??2???? 11???ss0?ss1?ss2????2130??1?22???1?1?11??6ss2???1111???1??ss0?ss1?ss2?ss3??ss3?266??2?6?接下来分解上面结果的最右端的矩阵，结合代码7，有
h0x0??1????2ss0??2??h0???h?hx?x?x??????201012?1ss??1???2??2???0?1???h?hx?x?x?ss2???01??012???0???6??6?0?1??h?2hx?2x?4x??1??012???ss3???0??6??6??0h0?h120000h0?h1600?x0???0???x?x?x012?0?????x0?x1?x2??h0?2h1??x?2x?4x12???06?