关于FNT乘法， 我想可能有点误会，想讨论的进来

gxqcn

原帖由 无心人 于 2008-4-17 21:18 发表 你说的例子叫三项式变换 确实是诱人 不过其$\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$太大了 太大的就不好利用

gxqcn

原帖由 无心人 于 2008-4-17 21:43 发表 另外，你的和我给出的都有缺点就是$N$太大了 太大的就不好利用

$N$ 的大小将决定一次变换可作的最大长度，当然是多多益善了！ $\alpha = 8$ 也并不能带来多大的收益， 因为在计算 $\alpha^r % M$ 时，也仅有极少的较小的 $r$ 可以快速计算， 且这个一般是用类似查表的方式解决，所以不要太在意 $\alpha$ 是否好算。

无心人

$N=2^32$你怎么利用啊 这个$N$，序列的长度必须严格是这么长啊 或者说，如果有序列长度短于它，则要补零到这个长度 则如果太短的序列，其效果就不如其他参数合适的NTT ================================================ 另外$\alpha$是$2$的幂时的变换是移位操作 所以不用额外表

gxqcn

你说反了，序列的长度是不能大于 $N$ 才对（经特殊处理，可达到 $3N$）。 “$\alpha$是$2$的幂时的变换是移位操作”，也仅能作有限次， 超出 $M$ 的大小后一样需要其它操作才能求出剩余。

无心人

用小于N的序列你如何做变换? $\alpha$是$2$幂时，如果$M$二进制表示简单，就有简化方法

liangbch

原帖由 gxqcn 于 2008-4-17 21:03 发表 我认为 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变换次数,最终运行速度反而提高了。 但不知，能否找到这样的质数模？

gxqcn

楼上说对了。 虽说失败了，但仍有很大收获：SIMD汇编入门了。