找回密码
 欢迎注册
楼主: 无心人

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

[复制链接]
发表于 2008-5-6 19:10:46 | 显示全部楼层
不是有个分段NTT的方法么?书上说的,把数据分段(原书是说因为早期的内存太小),同样能作NTT
当然会比一般的NTT慢,不过相当于2维NTT的水平
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 19:41:13 | 显示全部楼层
我现在明白用CRT和不用CRT的区别了
因为NTT最快的速度是O(n*Log(n)),
使用CRT的话,只有最后的O(n)用96bit运算;
不使用CRT,则整个O(n*Log(n))都要用96bit的运算.
这中间因该有个平衡!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-6 20:06:23 | 显示全部楼层


假设一个普通乘法工作量是c
则直接NTT为(logn此处实际为2为底的对数)
$3nlogn * (3 + 3c) + 2n* 3c + n$其中第一个3代表两次正变换,一次负变换,第二个三代表中间乘2的方幂,等于移位的工作量,2代表一次逆变换需要乘$1/N$和两次正变换的结果相乘, 最后一个$n$代表位序颠倒的工作量
使用CRT的
$9nlogn*2c + 3nc + 3n*6c + 3n$
========================================
备注,可能不准确
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-6 20:13:05 | 显示全部楼层
分段NTT不是目前考虑的问题了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 20:28:39 | 显示全部楼层
有一个数据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#是知道中国剩余定理的,只是为了简单才写成这样。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 20:48:27 | 显示全部楼层
回楼上:
看来你真的看的很认真
如果你不指出,这个错误可能就这么错下去了
在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

这下应该对了!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-6 20:55:35 | 显示全部楼层


对CRT俺没详细研究过
有一个乘法就是依赖于CRT而存在的
就是乘法的模算法
用六个模计算乘法

只要运算只用到乘法,就能从中得到好处
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 20:56:43 | 显示全部楼层
有一个数据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  !
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-6 21:06:51 | 显示全部楼层
为乘法而作的NTT可以不用像一般NTT那样要位序颠倒!
因为你使用NTT,使得位序乱了
但你又使用了个逆NTT,使得乱了的序又自动变回来了!


===================================================
可恶的新手每小时2贴限制
害的我不能回复了
就在这里编辑,来回复楼下吧!

对NTT不用位序颠倒我是试验过的,实际上我目前就是这么做的,结果当然是对的!

[ 本帖最后由 ssikkiss 于 2008-5-6 21:35 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-6 21:14:11 | 显示全部楼层




必须进行位序颠倒!!!!

TAOCP上就专门有个习题说这个问题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 00:56 , Processed in 0.058200 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表