不是素数的费马数
必须以2或者根号2为alpha
此时的幂乘就是移位
而且模费马数的运算实际上是个减法
怎么个减法?
费马数是 2^(2^b)+1 :Q: 假设$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之间的数字还是很大厄...:L
我还是安于现状吧...
毕竟用CRT的变换在VB6里挺快的...:lol :)
你可以考虑$2^{32n} + 1$类似的变换
长度可以随心了
但似乎结构复杂点 对了,还有件比较郁闷的事
假设a,b是长度为n的序列
那么c=a*b就是长度大约为2n的序列了
问题是我的乘法是限制精度的计算
也就是说对我有用的只有c的前n位
后面的n位就白算了:L
虽然说通过改变变换的顺序可以节省逆变换时的半个变换
但是那样就又得加上位翻转的:L
我矛盾死了:M:
普通的笔算方法是可以通过控制计算位来节省计算的
但是变换就不行了:'( :)
你要知道
只有完全计算n位数字相乘，才能得到结果的前n位的近似值
所以不能算白算
假设a = 1234
b = 5678
你笔算 如何得到 a * b的前4位？
回复 56# 无心人 的帖子
00001234*00005678
---------------
XXXXYYYY
显然我只要XXXX的值
从进位的角度看
对8而言,只有1有影响
对7而言,只有12有影响
对6而言,只有123有影响
对5而言,只有1234有影响
所有笔算的时候可以省掉小半的运算
假如数据足够长,只有最后的2,3位可能误差,前面的值是肯定正确的 :lol
那你完全可以模拟这个过程的
不过不能拆成一位（这里的一位指一个机器字）乘多位
否则效率不好 以前就是这么干的
因为是O(N^2)的所以想改成数论变换的
诶,世上果然没有完美的事... 你下载mpfr的代码看看它们如何处理的