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相关问题一则，有兴趣的参与