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

仙剑魔

原帖由 无心人 于 2008-9-6 18:02 发表 不是素数的费马数 必须以2或者根号2为alpha 此时的幂乘就是移位 而且模费马数的运算实际上是个减法

怎么个减法? 费马数是 2^(2^b)+1

无心人

假设$b = 10$ 则$F_10 = 2^{2^10} + 1 = 2^1024 + 1$ 显然$2^1024 -= -1 mod F_10$ 如果$m > F_10$ $m = a * 2^1024 + b$ 则$m mod F_10 = (a * 2^1024 + b) mod F_10 = (b - a) mod F_10$ 由于$1024 = 32 * 32 = 64 * 16$ 实际的减法是个很简单的长减法 在32位机器和64位机器上都很容易进行 只要考虑减后的结果在$0$和$F_10 - 1$之间就可以了 否则要重新调整

仙剑魔

看来FNT最大的缺点就是变换长度跳跃式增长... 不过0到F10-1之间的数字还是很大厄... 我还是安于现状吧... 毕竟用CRT的变换在VB6里挺快的...

无心人

你可以考虑$2^{32n} + 1$类似的变换 长度可以随心了 但似乎结构复杂点

仙剑魔

对了,还有件比较郁闷的事 假设a,b是长度为n的序列 那么c=a*b就是长度大约为2n的序列了 问题是我的乘法是限制精度的计算 也就是说对我有用的只有c的前n位 后面的n位就白算了 虽然说通过改变变换的顺序可以节省逆变换时的半个变换 但是那样就又得加上位翻转的 我矛盾死了 普通的笔算方法是可以通过控制计算位来节省计算的 但是变换就不行了

无心人

你要知道 只有完全计算n位数字相乘，才能得到结果的前n位的近似值 所以不能算白算 假设a = 1234 b = 5678 你笔算 如何得到 a * b的前4位？

仙剑魔

00001234 *00005678 --------------- XXXXYYYY 显然我只要XXXX的值 从进位的角度看 对8而言,只有1有影响 对7而言,只有12有影响 对6而言,只有123有影响 对5而言,只有1234有影响 所有笔算的时候可以省掉小半的运算 假如数据足够长,只有最后的2,3位可能误差,前面的值是肯定正确的

无心人

那你完全可以模拟这个过程的 不过不能拆成一位（这里的一位指一个机器字）乘多位 否则效率不好

仙剑魔

以前就是这么干的 因为是O(N^2)的所以想改成数论变换的 诶,世上果然没有完美的事...

无心人

你下载mpfr的代码看看它们如何处理的