请问一下各位老大阶乘的问题

winxos · 发表于 2010-2-16 10:31:42

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

我记忆中好像看到老大们讨论过，搜索了一下没搜到，用google也尽搜到一些很低水平的东西，我就重新问一下各位老大。对于指数的优化采用动态规划来做速度可以做到比较快，但是对于阶乘来说，由于涉及到素数的问题，所以我只想到了把阶乘$n! =2^{a_1}*3^{a_2}...p^{a_p}$来做，对于指数次数的计算也比较好计算，而且对于$p>\sqrt{n}$可以得到次方为简单的$[n/p]$ 我采用GMP库做了一下试验，在我电脑上计算 $100000!$ 用硬乘法需要58s，采用上面的算法需要29s左右，发现提速不是很大，但是我调用其内部的计算发现只需要2s，所以感到很困惑，竟然还有这么大的优化空间，请各位老大解释一下大概的思路？谢谢。

medie2005 · 发表于 2010-2-17 10:02:42

注意到FFT在乘数a,b长度相近的时候，效率最高。所以，阶乘算法要想高效，必须要让每次做FFT乘时，乘数长度项近。

gxqcn · 发表于 2010-2-20 07:57:40

阶乘虽然是一些数的连续乘法，但还是有不少讲究的。 1、尽可能调用平方函数，因为它比通用的乘法函数可以做更多的特别优化； 2、尽可能地多调用高阶算法函数，可以使总体算法复杂度降低。对于第2条，比如说，用硬乘法永远是“大数*小数”模式，无法享受到FFT等高阶算法带来的好处。

winxos · 发表于 2010-2-20 12:11:22

阶乘虽然是一些数的连续乘法，但还是有不少讲究的。 1、尽可能调用平方函数，因为它比通用的乘法函数可以做更多的特别优化； 2、尽可能地多调用高阶算法函数，可以使总体算法复杂度降低。对于第2条，比如说，用硬 ... gxqcn 发表于 2010-2-20 07:57

谢谢两位老大，我有时间一定好好学习一下FFT算法，到时候不解的地方可能还要麻烦各位老大指点^_^

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

[讨论] 请问一下各位老大阶乘的问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。