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

Question

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

prime = 2**74207281 - 1

大约需要半秒的时间，而且效果很好。操作也相当快。将它除以 10（不带小数）以快速移动数字。但是，str(prime) 花费了很长时间。我像这样重新实现了 str，发现它每秒处理大约一百个数字。

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

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

Answer 1

有 gmp，GNU 多精度算术库。它专为快速处理大量数据而设计。

Answer 2

重复的字符串连接是出了名的低效，因为 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")))

对我来说，这会打印（使用 Python 2.7.10）：

f1: 15.3430171013
f2: 20.8928260803
f3: 0.310356140137
f4: 2.80087995529

Answer 3

使用 WinGhci（Haskell 语言）输出文件大约用了 32 秒：

import System.IO

main = writeFile "prime.txt" (show (2^74207281 - 1))

文件大小为 21 MB；最后四位数字，6351.

Answer 4

Python 的整数到字符串的转换算法使用一个简单的算法，运行的复杂度为 O(n**2)。随着数字的长度加倍，转换时间翻两番。

我电脑上的一些简单测试显示运行ning 时间增加：

$ time py35 -c "n=str(2**1000000)"
user    0m1.808s
$ time py35 -c "n=str(2**2000000)"
user    0m7.128s
$ time py35 -c "n=str(2**4000000)"
user    0m28.444s
$ time py35 -c "n=str(2**8000000)"
user    1m54.164s

由于实际指数比我上次的测试值大10倍左右，所以应该要长100倍左右。或者只有 3 个多小时。

可以做得更快吗？是的。有几种方法更快。

方法一

用power-of-10 将非常大的数字分成两个大致equal-sized 但较小的数字会更快。重复该过程，直到数字相对较小。然后 str() 用于每个数字，前导零用于将结果填充到与最后一个 power-of-10 相同的长度。然后连接字符串以形成最终结果。此方法由 mpmath 库使用，文档暗示它应该快大约 3 倍。

方法二

Python的整数以二进制格式存储。二进制非常适合计算，但 binary-to-decimal 转换是瓶颈。可以定义您自己的整数类型，将值存储在 100 个（或类似值）十进制数字的块中。运算（指数、乘法、除法）会变慢，但转换为字符串会非常快。

很多年前，我实现了这样一个class，并使用了高效的乘法和除法算法。该代码不再在 Internet 上可用，但我确实找到了一个我测试过的备份副本。运行宁时间减少到 ~14 秒。

更新

我更新了上面引用的 DecInt 代码，现在可以在 https://github.com/casevh/DecInt。

如果使用Python的原生整数类型，在我的电脑上总的运行ning时间不到14秒。如果使用 gmpy2 的整数类型，则运行ning 时间约为 3.5 秒。

$ py35 DecInt.py
Calculating 2^74207281
Exponentiation time: 3.236
Conversion to decimal format: 0.304
Total elapsed time: 3.540
Length of result: 22338618 digits

方法三

我维护 gmpy2 库，可以轻松访问 GMP 库以进行快速整数运算。 GMP 在高度优化的 C 和汇编代码中实现方法 1，并在 ~5 秒内计算素数和字符串表示形式。

方法四

Python 中的 decimal 模块将值存储为十进制数字。 Python 3 的最新版本包含十进制库的 C 实现，它比 pure-Python 实现包含在 Python 2 中要快得多。C 实现运行仅需 3在我的电脑上秒。

from decimal import *
getcontext().prec = 23000000
getcontext().Emin = -999999999
getcontext().Emax = 999999999
x=Decimal(2)**74207281 - 1
s=str(x)

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

How can I convert an absolutely massive number to a string in a reasonable amount of time?

python

string

primes

biginteger