python 中缓慢的 Big Int 输出

Question

有没有办法提高 python 中“str(bigint)”和“print bigint”的性能？打印大整数值需要花费大量时间。我尝试使用以下递归技术：

def p(x,n):
    if n < 10:
            sys.stdout.write(str(x))
            return
    n >>= 1
    l = 10**n
    k = x/l
    p(k,n)
    p(x-k*l,n)

n = 位数， x = bigint

但在某些情况下，当子调用中的 x 具有前导零时，该方法会失败。有没有其他方法或者更快的方法。 （请不要建议使用任何外部模块或库）。

Answer 1

从 Python 整数到字符串的转换的运行时间为 O(n^2)，其中 n 是数字的长度。对于足够大的数量，速度会很慢。对于 1,000,001 位数字，str() 在我的计算机上大约需要 24 秒。

如果您确实需要将非常大的数字转换为字符串，那么递归算法是一个很好的方法。

以下版本的递归代码应该可以工作：

def p(x,n=0):
    if n == 0:
        n = int(x.bit_length() * 0.3)
    if n < 100:
        return str(x)
    n >>= 1
    l = 10**n
    a,b = divmod(x, l)
    upper = p(a,n)
    lower = p(b,n).rjust(n, "0")
    return upper + lower

它自动估计输出中的位数。对于 1,000,001 位数字，速度大约快 4 倍。

如果您需要更快，您可能需要使用外部库。

Answer 2

对于交互式应用程序，内置的 print 和 str 函数在眨眼间运行。

>>> print(2435**356)
392312129667763499898262143039114894750417507355276682533585134425186395679473824899297157270033375504856169200419790241076407862555973647354250524748912846623242257527142883035360865888685267386832304026227703002862158054991819517588882346178140891206845776401970463656725623839442836540489638768126315244542314683938913576544051925370624663114138982037489687849052948878188837292688265616405774377520006375994949701519494522395226583576242344239113115827276205685762765108568669292303049637000429363186413856005994770187918867698591851295816517558832718248949393330804685089066399603091911285844172167548214009780037628890526044957760742395926235582458565322761344968885262239207421474370777496310304525709023682281880997037864251638836009263968398622163509788100571164918283951366862838187930843528788482813390723672536414889756154950781741921331767254375186751657589782510334001427152820459605953449036021467737998917512341953008677012880972708316862112445813219301272179609511447382276509319506771439679815804130595523836440825373857906867090741932138749478241373687043584739886123984717258259445661838205364797315487681003613101753488707273055848670365977127506840194115511621930636465549468994140625
>>> str(2435**356)
'392312129667763499898262143039114894750417507355276682533585134425186395679473824899297157270033375504856169200419790241076407862555973647354250524748912846623242257527142883035360865888685267386832304026227703002862158054991819517588882346178140891206845776401970463656725623839442836540489638768126315244542314683938913576544051925370624663114138982037489687849052948878188837292688265616405774377520006375994949701519494522395226583576242344239113115827276205685762765108568669292303049637000429363186413856005994770187918867698591851295816517558832718248949393330804685089066399603091911285844172167548214009780037628890526044957760742395926235582458565322761344968885262239207421474370777496310304525709023682281880997037864251638836009263968398622163509788100571164918283951366862838187930843528788482813390723672536414889756154950781741921331767254375186751657589782510334001427152820459605953449036021467737998917512341953008677012880972708316862112445813219301272179609511447382276509319506771439679815804130595523836440825373857906867090741932138749478241373687043584739886123984717258259445661838205364797315487681003613101753488707273055848670365977127506840194115511621930636465549468994140625'

但是，如果您将大整数打印到（例如标准输出），以便另一个进程可以（从标准输入）读取它们，并且您发现二进制到十进制的操作会影响整体性能，那么您可以查看< a href="https://stackoverflow.com/questions/4358285/is-there-a-faster-way-to-convert-an-任意-large-integer-to-a-big-endian-seque">是有一个将任意大整数转换为大端字节序列的更快方法？ （尽管接受的答案建议 numpy，它是一个外部库，但还有其他建议）。