NTT相关问题一则，有兴趣的参与

gxqcn

可惜 2^n+1 型的素数少之又少， 也就是那五个已知的Fermat Prime（3、5、17、257、65537）， 要不在数论变换里可就大有作为了。 一般NTT是采用 k*2^b+1 型的素数， 虽然模运算麻烦了点， 但所需的临时空间比较小，总计算量也较小。

无心人

老大 FNT并不要求模是素数啊 不是素数的费马数 $alpha$值不能选3而已 但选择2才能简化运算的啊

无心人

FNT的缺点不是别的 就是参数可选择的范围小而已 相邻两个费尔马数的差别也太大了点 呵呵 详细的看我总结的表

仙剑魔

如果没有溢出保护是不是会自动进位啊? 现在我的大脑告诉我2方幂进制的结果肯定是正确的 但是其他的进制我就不确定的 刚想到这个方法,我现在还有点混乱 怎么说好 之前的CRT已经有点颠覆我的观念了 这回的这个对我是又一次的震撼 计算的中间过程似乎需要大量的内存空间? 比如 w=2^32,n=2^m k个元素的序列a[k]和b[k]做变换 每个元素中间计算结果都得用一个长度为n的数组来保存? 那之后的a[k]*b[k]要怎么办呀? 不可能做k次n*n的乘法吧

仙剑魔

素数只是为了搞出原根吧 放宽条件以后不是素数也能做变换的 变换长度为n的序列只要找到n重根就行了

无心人

乘法算法速度越快 要求的辅助空间越大 FNT乘法存在一个初始切分的问题 先切分成符合要求的每个数字都是固定长度的序列 所以要求的辅助空间就大了 不象 CRT 几乎可在原位置变换

仙剑魔

恩 但是后面那个卷积怎么办呀 太长的话就变成n^2的乘法了呀 难道再嵌套NTT ?!

无心人

PS: 突然有兴致去看机械键盘 发现好贵哦 800多 但似乎好好的样子 什么时候弄个来用啊

无心人

FNT中间的乘法太大 确实要用FNT再处理下啊

gxqcn

若这里“n^2”的 n 并不大，是一个较小的常整数时， 整体效率还是很好的。