回复 63# 仙剑魔 的帖子
可惜 2^n+1 型的素数少之又少，也就是那五个已知的Fermat Prime（3、5、17、257、65537），
要不在数论变换里可就大有作为了。
一般NTT是采用 k*2^b+1 型的素数，
虽然模运算麻烦了点，
但所需的临时空间比较小，总计算量也较小。 老大
FNT并不要求模是素数啊
不是素数的费马数
$alpha$值不能选3而已
但选择2才能简化运算的啊 FNT的缺点不是别的
就是参数可选择的范围小而已
相邻两个费尔马数的差别也太大了点
呵呵
详细的看我总结的表
回复 70# 无心人 的帖子
如果没有溢出保护是不是会自动进位啊?:lol现在我的大脑告诉我2方幂进制的结果肯定是正确的
但是其他的进制我就不确定的
刚想到这个方法,我现在还有点混乱
怎么说好
之前的CRT已经有点颠覆我的观念了
这回的这个对我是又一次的震撼
计算的中间过程似乎需要大量的内存空间?
比如
w=2^32,n=2^m
k个元素的序列a和b做变换
每个元素中间计算结果都得用一个长度为n的数组来保存?
那之后的a*b要怎么办呀?
不可能做k次n*n的乘法吧
回复 71# gxqcn 的帖子
素数只是为了搞出原根吧放宽条件以后不是素数也能做变换的
变换长度为n的序列只要找到n重根就行了 :)
乘法算法速度越快
要求的辅助空间越大
FNT乘法存在一个初始切分的问题
先切分成符合要求的每个数字都是固定长度的序列
所以要求的辅助空间就大了
不象 CRT 几乎可在原位置变换
回复 76# 无心人 的帖子
恩但是后面那个卷积怎么办呀
太长的话就变成n^2的乘法了呀
难道再嵌套NTT ?! PS:
突然有兴致去看机械键盘
发现好贵哦
800多
但似乎好好的样子
什么时候弄个来用啊
:( FNT中间的乘法太大
确实要用FNT再处理下啊
回复 77# 仙剑魔 的帖子
若这里“n^2”的 n 并不大，是一个较小的常整数时，整体效率还是很好的。