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

仙剑魔 · 发表于 2008-9-6 20:13:30

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

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

无心人 · 发表于 2008-9-7 08:49:11

假设$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$之间就可以了
否则要重新调整

仙剑魔 · 发表于 2008-9-7 10:39:01

看来FNT最大的缺点就是变换长度跳跃式增长...

不过0到F10-1之间的数字还是很大厄...

我还是安于现状吧...
毕竟用CRT的变换在VB6里挺快的...

无心人 · 发表于 2008-9-7 10:56:28

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

仙剑魔 · 发表于 2008-9-7 21:02:00

对了,还有件比较郁闷的事
假设a,b是长度为n的序列
那么c=a*b就是长度大约为2n的序列了
问题是我的乘法是限制精度的计算
也就是说对我有用的只有c的前n位
后面的n位就白算了

虽然说通过改变变换的顺序可以节省逆变换时的半个变换
但是那样就又得加上位翻转的

我矛盾死了

普通的笔算方法是可以通过控制计算位来节省计算的
但是变换就不行了

无心人 · 发表于 2008-9-8 08:07:03

你要知道
只有完全计算n位数字相乘，才能得到结果的前n位的近似值
所以不能算白算

假设a = 1234
b = 5678
你笔算如何得到 a * b的前4位？

仙剑魔 · 发表于 2008-9-8 10:35:52

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

无心人 · 发表于 2008-9-8 10:54:37

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

仙剑魔 · 发表于 2008-9-8 14:44:30

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

无心人 · 发表于 2008-9-8 21:13:12

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

账号		自动登录	找回密码
密码			欢迎注册

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

回复 56# 无心人的帖子

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

回复 56# 无心人 的帖子

回复 56# 无心人的帖子