请教一下 v 友们，关于 python2 和 python3 内部乘法的实现 s

[fool079]

最近在尝试寻找阶乘的最优解 无意间发现 py2 和 py3 调用 math.factorial 的时候在算大数（大概 10w-100w 的量级）阶乘的时候效率差距非常大。 然后因为自己在 py3 中实现了 primeSwing 是比内置库算阶乘要快的，而且实现的时候用的也是直接的乘法。 所以推断 py2 到 py3 的时候内部对于乘法的计算有了一些优化。

所以想请教一下 v 友们： 1、py2 到 py3 的内部乘法是有个什么样的优化； 2、目前的阶乘除了 primeSwing 还有什么更优的算法吗

[fool079]

为啥回车没用。。这个布局。。。

[bumz]

大数乘法已经不再是 O(1) 了，naive 的实现 O(n^2) (但是对小数效果还是不错的)

所以对于 N!，朴素乘法的朴素阶乘达到了 O(N^2 (log N)^2)

但是如果背后的乘法用 Karatsuba 甚至 fft，还会更快

[bumz]

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

[fool079]

@bumz 谢谢，不过我在 js 中实现了 ntt，然后发现把 ntt 应用在 1w 阶乘的时候比 BigInt 直接乘慢了大概 7w 倍。。(上述是 js 环境下，主题是 python 环境，没搞错)