一个循环卷积的问题

无心人

首先声明
此问题来头不小
但请先别看别的书籍和资料
先考虑下其中的东西

====================================================
    定义序列$(x_0, x_1, ..., x_{n-1})$和序列$(y_0, y_1, ..., y_{n-1})$的循环卷积为序列$(z_0, z_1, ..., z_{n-1})$,其中$z_k = x_0y_k + x_1y_{k-1} + ... + x_ky_0 + (x_{k+1}y_{n-1} + x_{k+2}y_{n-2} + ... + x_{n-1}y_{k+1})$。类似的定义反循环卷积，但$z_k = x_0y_k + x_1y_{k-1} + ... + x_ky_0 - (x_{k+1}y_{n-1} + x_{k+2}y_{n-2} + ... + x_{n-1}y_{k+1})$。
    当$n$为$2$的幂时，构造在整数上的循环和反循环卷积的快速算法。或者说有一个乘法是$O(nlogn)$，加减法和移位是$O(lognloglogn)$的算法求阶为n的循环和反循环卷积。
    （提示，阶为2n的循环卷积可归结为阶为n的循环和反循环卷积）

无心人

容易看出来

当两个序列的高半部分为0时
两个序列的这么定义的卷积等于乘法的定义

liangbch

我只知道循环卷积和线性卷积，很深入的推理，我就爱莫能助了。
By the way,昨天在论坛上花的时间太多了，今天需要好好干活了。

无心人

实话说了吧
这个问题是TAOCP上的习题
乃大数乘法的终极算法

解开了就得到一个完美的大数乘法

mathe

其中循环卷积$z_k = x_0y_k + x_1y_{k-1} + ... + x_ky_0 + (x_{k+1}y_{n-1} + x_{k+2}y_{n-2} + ... + x_{n-1}y_{k+1})$的计算应该比较简单一些。
如果我们定义$X_{1,k}=x_k+x_{k+n/2},  Y_{1,k}=y_k+y_{k+n/2},k=1,2,...,n/2$
                        $X_{2,k}=x_k-x_{k+n/2},  Y_{2,k}=y_k-y_{k+n/2},k=1,2,...,n/2$
那么分别对${X_1,Y_1}, {X_2,Y_2}$做循环卷积,做好的结果累加（相减是另外一部分）然后除以2就是结果了。
也就是是说，$n$阶问题可以分解为两个$n/2$阶问题（在加上O(n)时间的运算）,所以这个过程的时间复杂度是O(nlog(n))的。
但是上面过程有一个问题，那就是计算有可能会出现溢出。比如原先直接计算x和y的卷积，其和不会超过$2^32$，但是分解程两个序列卷积然后求和以后，由于结果乘了2，有可能会发生溢出问题。
对于这个问题，其实也不难解决。只要保证原先数据不会超出$2^32$，那么我们还是可以设计一个同样时间复杂度的算法。我们可以取两个比较大的奇数p,q使得$p*q>2^32,(p,q)=1$,然后分别对所有的上面计算过程关于p和q求模，而由于2和p,q都互素，所有的除2可以用乘上2的数论倒数替换。所以通过这种方法，我们最后在通过一次中国剩余定理可以计算出最终结果。

mathe

而关于另外一个问题（反循环卷积），感觉定义
$X_{1,k}$在$k<n/4$时为$x_k+x_{k+n/2}$而在$n/4<=k<n/2$时为$x_k-x_{k+n/2}$就应该可以了。不过可能不正确，需要大家自己去调整一下。
其实就5#的方法，我们可以将它想象成分别对两个序列x和y做离散小波变换（而不是傅立叶变换），变换完以后逐项相乘，乘完以后在做小波变换的逆变换就可以了。

无心人

小波变换么？
存在快速算法么？

溢出的问题可转换为高精度计算

mathe

高精度计算其实就等同于增加了计算复杂度。
一般说的小波变换就是Haar小波对应的变换，同离散傅立叶变换非常类似，有类似的快速算法。
对它进行推广可以推广到Hadamard矩阵，这些都比傅立叶变换更加适合整数中的运算。

无心人

Hadamard矩阵


竟然牵涉到这个啦

是否和高阶Hadamard矩阵相关？
要知道可能有些这种矩阵是尚未找到的

mathe

见http://mathworld.wolfram.com/HadamardMatrix.html
$2^n$阶Hadamard矩阵是容易构造的，但是其它阶的可能是比较难