python - 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 倍。

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