原帖由 无心人 于 2008-4-17 21:18 发表 http://images.5d6d.net/dz60/common/back.gif
你说的例子叫三项式变换
确实是诱人
不过其$\alpha, N$都是多少?
M = p = 2^96 - 2^32 + 1
N = 2^32
\alpha = \text{PrimitiveRoot}[ M ] = 11
因为$\alpha=11$所以不如NTT+CRT
这里有个简单的
$M=2^42+2^41+1, N=2^39,\alpha=8$
可惜$M$有点小哦
另外，你的和我给出的都有缺点就是$N$太大了
太大的就不好利用
原帖由 无心人 于 2008-4-17 21:43 发表 http://images.5d6d.net/dz60/common/back.gif
另外，你的和我给出的都有缺点就是$N$太大了
太大的就不好利用
N 的大小将决定一次变换可作的最大长度，当然是多多益善了！
\alpha = 8 也并不能带来多大的收益，
因为在计算 \alpha^r % M 时，也仅有极少的较小的 r 可以快速计算，
且这个一般是用类似查表的方式解决，所以不要太在意 \alpha 是否好算。
:)
$N=2^32$你怎么利用啊
这个$N$，序列的长度必须严格是这么长啊
或者说，如果有序列长度短于它，则要补零到这个长度
则如果太短的序列，其效果就不如其他参数合适的NTT
================================================
另外$\alpha$是$2$的幂时的变换是移位操作
所以不用额外表
你说反了，序列的长度是不能大于 $N$ 才对（经特殊处理，可达到 3N）。
“$\alpha$是$2$的幂时的变换是移位操作”，也仅能作有限次，
超出 M 的大小后一样需要其它操作才能求出剩余。
:)
用小于N的序列你如何做变换?
$\alpha$是$2$幂时，如果$M$二进制表示简单，就有简化方法
原帖由 gxqcn 于 2008-4-17 21:03 发表 http://images.5d6d.net/dz60/common/back.gif
我认为 joey5491 上面那句是占不住脚的。
因为我曾实现过以 p = 2^96 - 2^32 + 1 = 79 228 162 514 264 337 589 248 983 041 为模的 NTT，
此时因为 p 足够大，就完全避免了用 CRT（中国剩余定理）凑结果了，只需 ...
我明白了，去年这个时候，你那个 千分求汇编优化：UInt96x96To192(...) 就是为这个用的。
另外，虽然使用太大的模不能提高速度，但是当变换长度较小时，使用较大的质数模减少变换次数还是可能的。
假如，我们可以找到２个质数模，p1,p2, 使得p1xxp2~~10^19
那么，如果采用10^7进制，当被乘数和乘数长度小于10^5,则他们的线性卷积（被乘数和乘数的乘积）中的任一个数 均不超过p1*p2.因此我们仅仅可以使用2次变换，在应用CRT时，也只需要根据2个序列求最终结果了，虽然使用10^7进制，使得序列长度增加了，但由于减少了NTT变换次数,最终运行速度反而提高了。
但不知，能否找到这样的质数模？
楼上说对了。:lol
虽说失败了，但仍有很大收获：SIMD汇编入门了。:)