V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
fool079
V2EX  ›  程序员

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

  •  
  •   fool079 · 2019-11-09 16:09:40 +08:00 · 1448 次点击
    这是一个创建于 1601 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    4 条回复    2019-11-09 16:52:30 +08:00
    fool079
        1
    fool079  
    OP
       2019-11-09 16:10:11 +08:00
    为啥回车没用。。这个布局。。。
    bumz
        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,还会更快
    bumz
        3
    bumz  
       2019-11-09 16:45:13 +08:00 via iPhone
    fool079
        4
    fool079  
    OP
       2019-11-09 16:52:30 +08:00 via iPhone
    @bumz 谢谢,不过我在 js 中实现了 ntt,然后发现把 ntt 应用在 1w 阶乘的时候比 BigInt 直接乘慢了大概 7w 倍。。(上述是 js 环境下,主题是 python 环境,没搞错)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2689 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 15:47 · PVG 23:47 · LAX 08:47 · JFK 11:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.