如何在合理的时间内将绝对大数转换为字符串？

Z时代
2024-01-10
分类：问答

我知道这是一个很奇怪的问题，但是我正在尝试获取文件中当前最大质数的副本。以整数形式获取数字非常容易。我只是运行这个。

prime = 2**74207281 - 1

它大约需要半秒钟，并且工作正常。操作也相当快。将其除以10（不带小数）即可快速移动数字。但是，str(prime)需要很长时间。我str像这样重新实现，发现它每秒处理大约一百位数。

while prime > 0:
    strprime += str(prime%10)
    prime //= 10

有没有办法更有效地做到这一点？我在Python中执行此操作。我应该使用Python还是尝试一下，还是有更好的工具呢？

回答：

众所周知，重复的字符串连接效率很低，因为Python字符串是不可变的。我会去

strprime = str(prime)

以我的基准而言，这始终是最快的解决方案。这是我的小基准程序：

import decimal
def f1(x):
    ''' Definition by OP '''
    strprime = ""
    while x > 0:
        strprime += str(x%10)
        x //= 10
    return strprime
def digits(x):
    while x > 0:
        yield x % 10
        x //= 10
def f2(x):
    ''' Using string.join() to avoid repeated string concatenation '''
    return "".join((chr(48 + d) for d in digits(x)))
def f3(x):
    ''' Plain str() '''
    return str(x)
def f4(x):
    ''' Using Decimal class'''
    return decimal.Decimal(x).to_eng_string()
x = 2**100
if __name__ == '__main__':
    import timeit
    for i in range(1,5):
        funcName = "f" + str(i)
        print(funcName+ ": " + str(timeit.timeit(funcName + "(x)", setup="from __main__ import " + funcName + ", x")))