数论变换里 的进制的选择和M有什么关系?

knate

最近用快速数论变换写了一个阶乘的算法. 发觉 选择太大的b进制会有可能发生错误. (10000!,用10，100，1000进制计算正确,10000进制就错误了.) 感觉上似乎是数据发生了溢出. 这个进制的选择和M有什么关系要求. 从变换结果看似乎要求 b^3 < M 实际上是什么的要求呢,真的不懂. (选择的M 是(15<<27) + 1，似乎是31位内最大的一个了.)

knate

这个限制条件太宽了吧. 几乎达到 b^2 * N ^ 2. (b进制,N变换长度) 我见过有人发过 变换长度达 2^46,进制可达10^7(但不知道是不是同时可取到) 原话是这样的 "变换长度可达2^46(天文数字),进制可达1E7(1次可以算7位)" 其选取的M 是5000000000053*2^46+1.似乎是一个96bit左右的一个素数 但是他用的似乎是VB语言写的,不懂VB 我见过的似乎是一个上限是 k * b ^ 2 * N (k为一常数,b进制,N为变换长度,似乎和复数域的FFT误差分析很类似,但不敢肯定这个上限是否正确.) 我担心自己的思维进了死胡同,转不出来,于是上论坛问一下.

liangbch

若数组A[0..L-1]表示被乘数，数组B[0..L-1]表示被乘数，则积数组可表示为C[0,L+L-2],C[k]= sum(A[i]*B[j], i+j=k)。 为了使用数论变换计算大数乘法，需要 1.对数组A做一次变换长度为2L的FNT 2.对数组B做一次变换长度为2L的FNT 3.计算T[i]=A[i]*B[i], i=0..2L-2. 4.对T做一次变换长度为2L的逆变换,结果存储与C。 因为C[i]的最大值约为 (r-1)*(r-1)*L,故M的值应该大于 r^2*L,r为进制 如果r的值较大，就需要做多次大数的模乘法，再应用中国剩余定理得最终的乘积。 在apfloat，r的值达到10^9,而3个M的值均小于2^32,为了计算很大的数的乘机，它使用3个不同的M，做了3次大数模乘法（为了做两个大数的乘法，需要做6次FNT正变换，3次FNT逆变换），最后应用CRT得到了最终的结果。

knate

这样啊. 我原来的猜想是k * b ^ 2 * N是这个,但是感觉上这个范围还是太大,(N通常较大) 而且我看过少部分变换结果,似乎都不会小于b^3,所以才这样想的(b^2肯定是错的,),而且看到最后结果都能被N整除,似乎这个N可以省略(但这个细想似乎没有道理). 对了,提到10^9,我想多问一下.在做这三次模乘法的时候,应该是直接就用10^9进制的了.(这应该不算是问题) 在做这三次模乘法后 是先各项进行CRT组合再进行进制修正,还是这3个乘积各自先修正再组合然后结果再修正一次.? (好像这个问题比较小白,在翻你们以前的帖子时想到的.) 我刚看apfloat的2.41版本.,可惜到现在里面的基本关系都还没弄清楚

ssikkiss

刚找到一组三项式的素数： 1073741827:2^30+2^1+1 hex string:40000003 2147483647:2^31-2^1+1 hex string:7fffffff 1073741833:2^30+2^3+1 hex string:40000009 1073741857:2^30+2^5+1 hex string:40000021 2147483713:2^31+2^6+1 hex string:80000041 1073741953:2^30+2^7+1 hex string:40000081 2147483777:2^31+2^7+1 hex string:80000081 2147484161:2^31+2^9+1 hex string:80000201 2147483137:2^31-2^9+1 hex string:7ffffe01 1073750017:2^30+2^13+1 hex string:40002001 1073872897:2^30+2^17+1 hex string:40020001 2147352577:2^31-2^17+1 hex string:7ffe0001 1073479681:2^30-2^18+1 hex string:3ffc0001 1074266113:2^30+2^19+1 hex string:40080001 2146959361:2^31-2^19+1 hex string:7ff80001 4293918721:2^32-2^20+1 hex string:fff00001 2151677953:2^31+2^22+1 hex string:80400001 2130706433:2^31-2^24+1 hex string:7f000001 1107296257:2^30+2^25+1 hex string:42000001 2113929217:2^31-2^25+1 hex string:7e000001 2281701377:2^31+2^27+1 hex string:88000001 2013265921:2^31-2^27+1 hex string:78000001 3221225473:2^31+2^30+1 hex string:c0000001 3221225473:2^32-2^30+1 hex string:c0000001 find prime number :24 据说其二进制值0越多求模越快 但我粗测了下，发现差别不大，其中前面几个数明显稍慢

无心人

我并不认为 太小的模 有多大的用处 实用的数论变换，都是用一个很大的模做的 而中间的乘法，是用那些经过实践验证在小规模上 胜过数论变换和FFT傅里叶变换的算法的，像toom等算法 足够小的模会带来计算速度的降低的 我决的，怎么也要在10000位二进制以上的规模上 应用类FFT算法才比较合算，毕竟该类算法的预计算是比较繁琐的 至于模数的选择，我倾向于2^n + 1，因为足够简单

无心人

实践上应该是这么取舍的 超大规模，是浮点的傅里叶变换，大规模是FNT数论变换，然后中规模是Toom算法，小规模是Karatsuba乘法，极小的规模是硬乘。 这些算法，是从大到小的迭代调用关系，有一个统一的外壳根据规模自动选择

knate

我自己写的程序 小的直接就硬乘. 稍大一点的就用用费马变换.(感觉规模小的时候乘法真的影响速度,可能给自己写的效率有关系) 然后就是分治. 1024位(10进制数)以上就用快速数论变换. 太大没有条件测试了,想进一步提速,就发生了这贴的问题. (现在还没有能力看明白CRT,CRT的原理倒基本看得明白什么意思.) 昨晚看到 Decimal 数据类型,如果是硬件能够支持,那就太恐怖(29位)了. 不过好像不是基本类型.

knate

等把CRT的弄出来后按 无心人 的实现一下TOOM算法(这个没有写出来过,) 不过估计是一两个星期后的事了.

无心人

你说的费马变换是FNT么？那个比分治高级吧 不应该在你说的位置 ============================= Toom论坛有论文，有具体的实现算法 GMP实现了Toom-3,4,5,6算法 可以大大减少必须用FFT（整数的）的几率