无心人 发表于 2008-9-19 20:38:37

比如你算20000亿长度的乘法
估计至少要进行三层的FNT的
呵呵

无心人 发表于 2008-9-19 20:41:25

80#老大说的有道理

乘法存在一个算法链
不同规模的乘法对应不同的算法

如果算法中间需要乘法
也要在这个算法链中寻找合适的乘法算法

所以很长的乘法
其中的算法调用是很复杂的
不同算法相互调用很常见
当然要有一个协调的函数存在

仙剑魔 发表于 2008-9-19 20:42:26

回复 80# gxqcn 的帖子

没办法的
你看做变换么肯定要求n可以在比较大的范围里变动
至少也要能到2^20吧,n^2是不行的了
估计能接受的n不超过2^8,那样太短的:L

诶...
我放弃的...
这个方法不应该存在于这个世界上...:'(

无心人 发表于 2008-9-19 20:47:01

普通乘法算法
或者叫硬乘法
并不是很弱的一个算法

比如P4的U
在32个以下的双字
硬乘是最快的

当然不同的U对应不同的限制
超过限制的数字就要采取快速算法了
页: 1 2 3 4 5 6 7 8 [9]
查看完整版本: NTT相关问题一则，有兴趣的参与