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

仙剑魔 · 发表于 2008-9-8 23:46:21

估计好的方法都是分段的
小的时候直接乘
大了用2分
太大了开变换
于是代码就疯涨...

无心人 · 发表于 2008-9-9 14:41:39

呵呵

仙剑魔 · 发表于 2008-9-19 16:12:58

令 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位的数组来储存的话
乘法就只是下标的移动
但是加减就必须来个循环

无心人 · 发表于 2008-9-19 16:54:33

不

乘法还是乘法
求余简单了而已

FNT中没乘法的
就移位和求余

仙剑魔 · 发表于 2008-9-19 17:00:58

你看如果 w=2^32
如果我对一个数组a[]做乘法去乘w^n
那么相当于把a[]里每个元素的下标移动n个
对不对啊?

无心人 · 发表于 2008-9-19 17:05:05

那叫移位操作
相当于折叠后减

仙剑魔 · 发表于 2008-9-19 17:09:41

但是这样做好象加减会变慢...
果然是鱼和熊掌...

无心人 · 发表于 2008-9-19 17:20:11

对于普通的整数FFT
加减都是要求余的

加减都要最后通过求余调整
在概率意义下FNT加减法
其操作应该是一个机器字的减法
而不是长减法
所以要大大简单化了

所以并不复杂

仙剑魔 · 发表于 2008-9-19 18:11:49

那么那个数组里的数字是按什么进制存放的呀?
按2^32进制的话似乎得考虑进退位?

无心人 · 发表于 2008-9-19 20:07:37

是啊

如果是别的非2方幂的进制
就么这么多简化了

而且2的方幂也必须是2^16 2^32类似的
否则效率也不高啊

进位并不可怕
在C语言里也能完全用2^32位处理

你只要记住
a + b = c
如果在C语言里
c < a则肯定产生了进位

账号		自动登录	找回密码
密码			欢迎注册

[讨论] NTT相关问题一则，有兴趣的参与