在 python 中进行大计算时出现分段错误

Question

我想计算一些非常大的数字的 collatz 序列，但我想 python 无法处理这么大的数字，我不知道如何处理它。

这是我的程序：

def collatz(n):
    if (n == -1 or n == 1 or n == -17 or n == -17 -2**4096):
        print('break found',n)
        return
    if str(n)[-1] in ['1','3','5','7','9']:
        #print(n)
        return collatz(3*n + 1)
    else:
        return collatz(n//2)

我想使用 n = 2**4096 范围内的号码。我通过 sys.setrecursionlimit 函数增加了递归限制。但是现在我遇到了分段错误。

>>> sys.setrecursionlimit(10**9)
>>> collatz(2**1000 + 1)
break found: 1
>>> collatz(2**4000 + 1)
Segmentation fault (core dumped)

请给我一些关于我需要修改以实现大输入支持的建议..

Answer 1

让它成为非递归的，太深的递归会溢出堆栈，堆栈通常只有几兆字节。堆栈溢出后，您的程序因分段错误而崩溃。

您的代码已修改为非递归（不会崩溃）：

Try it online!

def collatz(n):
    while True:
        if (n == -1 or n == 1 or n == -17 or n == -17 -2**4096):
            print('break found', n)
            return
        if str(n)[-1] in ['1','3','5','7','9']:
            #print(n)
            n = 3 * n + 1
        else:
            n = n // 2


collatz(2**4000 + 1)

输出：

break found 1

顺便说一句，经典的 Collatz 问题可以用更短更快的代码来解决，例如：

Try it online!

def collatz(n):
    for i in range(1 << 50):
        if n == 1:
            return i
        n = 3 * n + 1 if n & 1 else n >> 1

print('Collatz chain length:', collatz(2**4000 + 1))

输出：

Collatz chain length: 29400

另外，我想提一下 Python 库 GMPY2 based on famous C-based GMP。它有非常优化的长整数算术代码，如果你真的需要速度，可以用来提升你的代码。

在 Windows 上可以通过下载 from here 并通过 pip install gmpy2‑2.0.8‑cp39‑cp39‑win_amd64.whl 安装 gmpy2。在 Linux 上可以通过 sudo apt install python3-gmpy2.

安装

安装后，您可以以非常简单的方式使用 gmpy2，例如下面的函数 collatz_gmpy()：

Try it online!

def collatz_py(n):
    for i in range(1 << 50):
        if n == 1:
            return i
        n = 3 * n + 1 if n & 1 else n >> 1

def collatz_gmpy(n):
    from gmpy2 import mpz
    n = mpz(n)
    for i in range(1 << 50):
        if n == 1:
            return i
        n = 3 * n + 1 if n & 1 else n >> 1

def test():
    import timeit
    n = 2 ** 100000 + 1
    for i, f in enumerate([collatz_py, collatz_gmpy]):
        print(f.__name__, round(timeit.timeit(lambda: f(n), number = 1), 3), 'secs')

test()

输出：

collatz_py 7.477 secs
collatz_gmpy 2.916 secs

正如您所见，GMPY2 变体与常规 Python 的变体相比提供了 2.56x 倍的加速。

Answer 2

我会写成：

def collatz(n):
    tmp = -17 - 2**4096            # precompute constant value outside loop
    while 1:                       # in general, iteration is better than recursion in Python for these kinds of functions
        if n in (-1, 1, -17, tmp): # less typing than lots of or clauses
            return n               # return values rather than printing them
        elif n % 2 == 1:           # faster than converting to string and checking last digit
            n = 3*n + 1
        else:
            n //= 2

调用它例如：

print(collatz(2**4000 + 1))

performance: 在我的电脑上，collatz(2**5000-1) 上面的代码需要 0.069 秒。将代码更改为 elif str(n)[-1] in '13579': 需要 1.606 秒，即慢 23 倍。

在 collatz(2**40000-1)，上面的代码使用了 3.822 秒。改变

elif n % 2 == 1:

要么

elif n % 2:

或

elif n & 1:

将时间减少到 1.988 秒（即没有差异）。

将 n //= 2 更改为 n >>= 1 将时间进一步减少到 1.506 秒。

在 python 中进行大计算时出现分段错误

Segmentation Fault Error while doing big calculations in python

python

segmentation-fault

collatz