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

ssikkiss

不是有个分段NTT的方法么?书上说的,把数据分段(原书是说因为早期的内存太小),同样能作NTT 当然会比一般的NTT慢,不过相当于2维NTT的水平

ssikkiss

我现在明白用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不是目前考虑的问题了

liangbch

有一个数据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#是知道中国剩余定理的，只是为了简单才写成这样。

ssikkiss

回楼上: 看来你真的看的很认真 如果你不指出,这个错误可能就这么错下去了 在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而存在的 就是乘法的模算法 用六个模计算乘法 只要运算只用到乘法，就能从中得到好处

ssikkiss

有一个数据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

ssikkiss

为乘法而作的NTT可以不用像一般NTT那样要位序颠倒! 因为你使用NTT,使得位序乱了 但你又使用了个逆NTT,使得乱了的序又自动变回来了! =================================================== 可恶的新手每小时2贴限制 害的我不能回复了 就在这里编辑,来回复楼下吧! 对NTT不用位序颠倒我是试验过的,实际上我目前就是这么做的,结果当然是对的! [ 本帖最后由 ssikkiss 于 2008-5-6 21:35 编辑 ]

无心人

不 必须进行位序颠倒！！！！ TAOCP上就专门有个习题说这个问题