python - Python 中的 n**n**n 启发式

Question

我只是玩弄 Python 并发现了一件有趣的事情:我的计算机(i5，3 GHz)在尝试计算 10 ** 10 ** 10 几个小时后就停止运行了。我知道数学不是创建 Python 的目的，但我想知道是否有办法帮助 Python 计算它。

到目前为止，我的观察结果是:n ** (2** lg(n**n)) 比 n ** n ** n< 快 2 倍

n = 8 ** (8 ** 8)
n2 = 8 ** (2 ** 24)
# measured by timeit
> 4.449993866728619e-07
> 1.8300124793313444e-07

---

1) 有没有人知道如何以最复杂的方式解决 n ** n ** n？

2) 生成器是否可以帮助减少内存滥用？

Answer 1

10 ** 10 ** 10 是一个非常非常大的数。 Python 正在尝试分配足够的内存来表示该数字。 10.000.000.000(100 亿)位数字占用的内存比您的计算机一次性提供的内存要多得多，因此您的计算机现在正在将内存换出到磁盘以腾出空间，这就是现在速度非常非常慢的原因。

为了说明，尝试对一些适合的数字使用 sys.getsizeof():

>>> import sys
>>> sys.getsizeof(10 ** 10 ** 6)
442948
>>> sys.getsizeof(10 ** 10 ** 7)
4429264

因此，额外的数字需要大约 10 倍的内存。上面的数量以字节为单位，所以 100 万位数字几乎需要半兆字节，1000 万位数字需要 4 兆字节。 Extrapoliting，您的号码需要 4 GB 的内存。 Python 是否会获得那么大的内存，这取决于您的操作系统和硬件。

Python 将整数存储在 increments of 30 bits 中在现代平台上；所以每 30 位需要额外的 4 个字节的存储空间。对于归结为 (log2(10 ** 10 ** 10) / 30 * 4) / (1024 ** 3) 的 100 亿位数字== 大约 4.125GiB。

您不能使用 Python 来表示这么大的数字。甚至 float 也达不到那么高:

>>> 10.0 ** 10 ** 10
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: (34, 'Result too large')

我不太熟悉 Python 中的 bignum(大数)处理；也许是 gmpy libray有设施来表示更好的数字。