数论变换和傅立叶变换一样有基时分和基频分2种算法
基时分是先倒位序再用蝴蝶形算法
基频分是先用蝴蝶形算法再倒位序
所以只要先用基频分做正变换再用基时分做逆变换,就可以省略倒位序的过程:lol 受教受教
呵呵 用CRT是怎么个情况呀
是不是中间计算的时候有a*b%c的时候,为了弥补这个乘法变量字长不够用的?
我不是很清楚CRT的作用 CRT乃中国剩余定理也
是用三个不同参数但变换长度相等的变换
最后以CRT得到最终结果
以达到减少字长，简化运算的目的啊
请看俺数论变换的那个帖子
应该有相关介绍吧
回复 44# 无心人 的帖子
有点了解是怎么回事了我一直在用单个变量长度计算
诶...真狭隘...就因为这个我一直在考虑增加字长又要避免益出:( 你考虑在相同的变换长度上，最简单的变换是 FNT，速度也最快
但缺点是变换长度固定
在我那个帖子里有相应的FNT变换参数列表
FNT迭代意义下的大数字乘法是最优化的
但有点失之于复杂了
相对于CRT和FFT（整数意义下的模2^n + 1）
也存在不同程度的空间复杂度的增加
而CRT特点在于变换代码不涉及大数字运算
仅中间步骤乘法有部分小的大整数的运算
但需要进行至少三次的不同参数的变换
参数的选择面受限于变换长度的限制
可选择的参数有限，且alpha的值很可能不是2的幂
基于模2^n + 1的变换则可能处于CRT数论变换和FNT之间吧
====================================
是我粗略的理解
并没仔细的思考
如有错误请指正 学会了..
用了CRT以后就相当于同步进行3个变换了
我为了中间计算不超出32字节,特意挑选了特殊的素数
p=a*2^b+1=k^2+1,这样a必须是平方数,b必须是偶数...
但是最后用CRT的组装的中间计算挺麻烦的
我做1E8进制的变换,组装后的结果大约有15-16的十进制位,但是中间计算却有20+的十进制位
这个地方让我很不爽...:L :lol
那你就实现FNT吧
那个没乘法的
光加减和移位操作就能完成的 FNT的参数不知道怎么选
费马数不是从第5个开始不是素数的么
原根,变换长度我就晕的...:'(
还有我搞不清那个移位的确切价值
貌似就算可以移位还是要算 mod p 的
而且如果移位了我就不能用那个减小中间运算大小的方法了:L
最关键的问题:
目前最擅长的还是VB6,没有移位,所以白搭:lol 不是素数的费马数
必须以2或者根号2为alpha
此时的幂乘就是移位
而且模费马数的运算实际上是个减法