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

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

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

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

80#老大说的有道理

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

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

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

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

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

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

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

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

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

当然不同的U对应不同的限制
超过限制的数字就要采取快速算法了

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

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