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

winxos

我记忆中好像看到老大们讨论过，搜索了一下没搜到，用google也尽搜到一些很低水平的东西，我就重新问一下各位老大。
对于指数的优化采用动态规划来做速度可以做到比较快，但是对于阶乘来说，由于涉及到素数的问题，所以我只想到了把阶乘$n! =2^{a_1}*3^{a_2}...p^{a_p}$来做，
对于指数次数的计算也比较好计算，而且对于$p>\sqrt{n}$可以得到次方为简单的$[n/p]$

我采用GMP库做了一下试验，在我电脑上计算 $100000!$ 用硬乘法需要58s，采用上面的算法需要29s左右，发现提速不是很大，但是我调用其内部的计算发现只需要2s，所以感到很困惑，竟然还有这么大的优化空间，请各位老大解释一下大概的思路？
谢谢。

medie2005

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

gxqcn

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

winxos

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

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