回复 60# 无心人 的帖子
估计好的方法都是分段的小的时候直接乘
大了用2分
太大了开变换
于是代码就疯涨... 呵呵
不知道我这样想对不对:
令 p=2^(16n)+1=>2^(16n) mod p=-1
=>2^(32n) mod p=1
令 w=2^32
=>w^n mod p=1
令 n=2^m 以实现快速算法
用一个32位的数组来储存的话
乘法就只是下标的移动
但是加减就必须来个循环 不
乘法还是乘法
求余简单了而已
FNT中没乘法的
就移位和求余
回复 64# 无心人 的帖子
你看如果 w=2^32如果我对一个数组a[]做乘法去乘w^n
那么相当于把a[]里每个元素的下标移动n个
对不对啊? :)
那叫移位操作
相当于折叠后减 但是这样做好象加减会变慢...
果然是鱼和熊掌... 对于普通的整数FFT
加减都是要求余的
加减都要最后通过求余调整
在概率意义下FNT加减法
其操作应该是一个机器字的减法
而不是长减法
所以要大大简单化了
所以并不复杂
回复 68# 无心人 的帖子
那么那个数组里的数字是按什么进制存放的呀?按2^32进制的话似乎得考虑进退位? :)
是啊
如果是别的非2方幂的进制
就么这么多简化了
而且2的方幂也必须是2^16 2^32类似的
否则效率也不高啊
进位并不可怕
在C语言里也能完全用2^32位处理
你只要记住
a + b = c
如果在C语言里
c < a则肯定产生了进位