数论变换里 的进制的选择和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（整数的）的几率