不是有个分段NTT的方法么?书上说的,把数据分段(原书是说因为早期的内存太小),同样能作NTT
当然会比一般的NTT慢,不过相当于2维NTT的水平
我现在明白用CRT和不用CRT的区别了
因为NTT最快的速度是O(n*Log(n)),
使用CRT的话,只有最后的O(n)用96bit运算;
不使用CRT,则整个O(n*Log(n))都要用96bit的运算.
这中间因该有个平衡!
:)
假设一个普通乘法工作量是c
则直接NTT为(logn此处实际为2为底的对数)
$3nlogn * (3 + 3c) + 2n* 3c + n$其中第一个3代表两次正变换，一次负变换，第二个三代表中间乘2的方幂，等于移位的工作量，2代表一次逆变换需要乘$1/N$和两次正变换的结果相乘， 最后一个$n$代表位序颠倒的工作量
使用CRT的
$9nlogn*2c + 3nc + 3n*6c + 3n$
========================================
备注，可能不准确
分段NTT不是目前考虑的问题了
有一个数据A,A < M
求p1= A mod m1,p2= A mod m2,p3=A mod m3 ;在这一步里,因为模是DWORD型的数据,是很好计算的
然后求B=p1*m2*m3+p2*m1*m3+p3*m1*m2 ;这里已经超出计算机字长,并不好算!
再求X = B mod M ;这里也超出计算机字长,并不好算!
则 A=X ;(CRT完成)
其中CRT的计算方法有问题？
引用一首中国古代的关于中国剩余定理的描述。
三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。
解释：
这是解决此类问题的方法，问题是，今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？
诗的解释：
三人同行七十稀，把除以3所得的余数用70乘。
五树梅花日一枝，把除以5所得的余数用21乘。
七子团圆正半月，把除以7所得的余数用15剩。
除百零五便得知，把上述三个积加起来，减去105的倍数，所得的差即为所求。
列式为：2×70＋3×21＋2×15=233，233－105×2=23。
使用24# 楼的记法，用数学公式描述：
问题：m1=3, m2=5, m3=7,A % m1 = 2 =p1, A % m2 =3= p2,A % p3 =2=p3, 求A
解法：A= (p1* 70 + p2*21 + p3* 15) % (m1*m2*m3)
值得注意的是：
此处70 并不等于 m2*m3(5*7=35),故B= p1*m2*m3+p2*m1*m3+p3*m1*m2 是有问题的。
中国剩余定理正确的解法：
设有同余方程组X=ai(mod mi),其中（mi,mj）=1，则此方程组有唯一解X=n1*a1+n2*a2+……+nk*ak，
其中ni=pi*yi，pi=m1*m2*…*mk/mi，yi是pi*yi=1（mod mi）的解。（i,j=1，2，………，k，i〈j）
注意，其中含有mod的等式中的“=”应视为同余等！
对于上面的题目，
m1=3, p1=3*5*7/3=35, 当y1=2时， p1*y1=70, 故p1*y1 =1(mod m1) 。
24# 错在，假定yi总是等于1。或许24#是知道中国剩余定理的，只是为了简单才写成这样。
回楼上:
看来你真的看的很认真
如果你不指出,这个错误可能就这么错下去了
在24楼里,我先算了的k1,k2,k3,后面都忘了写了,不好意思,应该是这样的:
B=p1*m2*m3+p2*m1*m3+p3*m1*m2
改为
B=p1*k1*m2*m3+p2*k2*m1*m3+p3*k3*m1*m2
这下应该对了!
:)
对CRT俺没详细研究过
有一个乘法就是依赖于CRT而存在的
就是乘法的模算法
用六个模计算乘法
只要运算只用到乘法，就能从中得到好处
有一个数据A,A < M
求p1= A mod m1,p2= A mod m2,p3=A mod m3 ;在这一步里,因为模是DWORD型的数据,是很好计算的
然后求B=p1*k1*m2*m3+p2*k2*m1*m3+p3*k3*m1*m2 ;这里已经超出计算机字长,并不好算!
再求X = B mod M ;这里也超出计算机字长,并不好算!
则 A=X ;(CRT完成)
这里我还有个错误,因为A < M,
所以再求X = B mod M ;这里也超出计算机字长,并不好算!这句不对,
B直接就等于A了,因为A<M!
为乘法而作的NTT可以不用像一般NTT那样要位序颠倒!
因为你使用NTT,使得位序乱了
但你又使用了个逆NTT,使得乱了的序又自动变回来了!
===================================================
可恶的新手每小时2贴限制
害的我不能回复了
就在这里编辑,来回复楼下吧!
对NTT不用位序颠倒我是试验过的,实际上我目前就是这么做的,结果当然是对的!
[ 本帖最后由 ssikkiss 于 2008-5-6 21:35 编辑 ]
:lol
不
必须进行位序颠倒！！！！
TAOCP上就专门有个习题说这个问题