在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

使其非递归，过深的递归溢出堆栈，堆栈通常只有几兆字节。堆栈溢出后，程序会因分段错误而崩溃。

您的代码被修改为非递归(不会崩溃(：

在线试用！

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

---

BTW，经典的Collatz问题可以用更短更快的代码来解决，例如：

在线试用！

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

---

此外，我想提及基于著名的基于C的GMP的Python库GMPY2。它有非常优化的长整数算法代码，如果你真的需要速度，可以用来提高你的代码。

在Windows上，gmpy2可以从这里下载并通过pip install gmpy2‑2.0.8‑cp39‑cp39‑win_amd64.whl安装。在Linux上，它可以通过sudo apt install python3-gmpy2进行安装。

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

在线试用！

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

可以看出，与常规Python的变体相比，GMPY2变体的2.56x速度提高了6倍。

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))

性能：在我的电脑上，具有上述代码的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秒。