这是一个创建于 1841 天前的主题，其中的信息可能已经有所发展或是发生改变。
最近在尝试寻找阶乘的最优解 无意间发现 py2 和 py3 调用 math.factorial 的时候在算大数（大概 10w-100w 的量级）阶乘的时候效率差距非常大。 然后因为自己在 py3 中实现了 primeSwing 是比内置库算阶乘要快的，而且实现的时候用的也是直接的乘法。 所以推断 py2 到 py3 的时候内部对于乘法的计算有了一些优化。
所以想请教一下 v 友们： 1、py2 到 py3 的内部乘法是有个什么样的优化； 2、目前的阶乘除了 primeSwing 还有什么更优的算法吗
 |
1
fool079 OP 为啥回车没用。。这个布局。。。
|
 |
2
bumz 2019-11-09 16:42:27 +08:00 via iPhone
大数乘法已经不再是 O(1) 了，naive 的实现 O(n^2) (但是对小数效果还是不错的)
所以对于 N!，朴素乘法的朴素阶乘达到了 O(N^2 (log N)^2) 但是如果背后的乘法用 Karatsuba 甚至 fft，还会更快 |
|
3
bumz 2019-11-09 16:45:13 +08:00 via iPhone
https://stackoverflow.com/questions/9815252/why-is-math-factorial-much-slower-in-python-2-x-than-3-x
Python 3 的阶乘用的 divide-and-conquer https://stackoverflow.com/questions/21957363/why-is-pythons-built-in-multiplication-so-fast 对于大数乘法用的是 Karatsuba |
Select Language