6

模块中使用的 Mersenne Twister 的周期random是（我被告知）2**19937 - 1。作为二进制数，即连续 19937 个 '1（如果我没记错的话）。Python 非常快地将其转换为十进制：

$ python -m timeit '2**19937'
10000000 loops, best of 3: 0.0271 usec per loop

$ python -m timeit -s 'result = 0' 'result += 2**19937'
100000 loops, best of 3: 2.09 usec per loop

我猜第二个版本是需要转换的版本？

它不仅仅是二进制的。这也很快。（而不是显示数字，我显示转换为字符串的小数长度）：

>>> import math
>>> N = 1000
>>> s = str((int(N*math.e))**(int(N*math.pi)))
>>> len(s)
10787
>>> N = 5000
>>> s = str((int(N*math.e))**(int(N*math.pi)))
>>> len(s)
64921

定时：

python -m timeit -s 'import math' -s 'N=1000' 's = str((int(N*math.e))**(int(N*math.pi)))'
10 loops, best of 3: 51.2 msec per loop

问题是：这实际上是如何完成的？

我只是天真地被打动了吗？我发现 Python shell 在瞬间生成大约 5000 个位置的景象真的很壮观。

编辑：

@dalke 和 @truppo 建议的其他时间

$ python -m timeit 'x=2' 'x**19937'
1000 loops, best of 3: 230 usec per loop
$ python -m timeit 'x=2' 'int(x**19937)'
1000 loops, best of 3: 232 usec per loop
$ python -m timeit 'x=2' 'str(x**19937)'
100 loops, best of 3: 16.6 msec per loop

$ python -m timeit -s 'result = 0' 'x = 2' 'result += x**19937'
1000 loops, best of 3: 237 usec per loop
$ python -m timeit -s 'result = 0' 'x = 2' 'result += x**19937' 'int(result)'
1000 loops, best of 3: 238 usec per loop
$ python -m timeit -s 'result = 0' 'x = 2' 'result += x**19937' 'str(result)'
100 loops, best of 3: 16.6 msec per loop

因此，在我看来，这result = 0; result += 2**19937可能确实会强制转换。

4

4 回答 4

6

讨厌在你的游行中下雨，但它这么快的原因是因为数学模块实际上没有在 Python 中实现。

Python 支持加载导出 Python API 但以其他语言实现的共享库。math.so 提供了您从中获得的模块import math，恰好是其中之一（_random.so 也是如此）。

于 2010-01-23T23:27:00.313 回答
5

编译为字节码时，常量表达式如2**19937将优化为单个常量：

>>> def foo(): return 2**10
... 
>>> import dis
>>> dis.dis(foo)
  1           0 LOAD_CONST               3 (1024)
              3 RETURN_VALUE        
>>>

改为考虑：

[~] python -m timeit 'x=2' 'x**19937'
1000 loops, best of 3: 210 usec per loop
于 2010-01-23T23:49:35.697 回答
4

Python 将其转换为十进制非常快。

我不知道 Python，但不，它不需要那样做。2^19937 不需要计算，它只是与 19937 的二进制移位（“<<”），所以它非常快。只有当您以十进制打印时，实际转换才是必要的，而且速度要慢得多。

编辑：如果数字基数与指数基数相同，则求幂可以与移位（=移动点）相同。

10^-1 = 0.1 10^0 = 1
10^1 = 10
10^2 = 100
10^3 = 1000
10^n = 1（n 个零）

您会看到 10 与指数 n 的幂运算只是移动了数字。现在计算机大多使用内部基数 2 (bits) ，因此计算 2^19937 是在位置 19937 中设置一个位（从零开始计数位位置）。
作为附加信息：转换为十进制通常是通过征服和除法算法来实现的，该算法连续地将数字除以十的幂。如您所见，实际转换速度要慢半百万。

第二个例子更有趣：当你用大整数 m 计算 m^n 时，最快的方法是将它连续相乘并存储临时结果。

示例：10^345

a = 10^2
b = a a = 10^4
c = b b = 10^16
d = c*c = 10^256

结果 = d c c c c c c c b b * 10

（可以进一步优化：参见 Knuth, Seminumerical Algorithms）

所以你只需要很长的乘法就可以很有效地计算出来。

编辑：乘法的确切实现取决于：除了正常的学校乘法 Karatsuba 之外，还使用了 Tom-Cooke 和 Schoenhagen-Strasse (FFT) 乘法。

于 2010-01-23T23:48:54.310 回答
0

我对这在 Python 中是如何实际实现的几乎一无所知，但鉴于这基本上是原始乘法和对数，即使在相当大的数字上它也相当快，我并不感到非常惊讶。

有任意精度的数学库，例如GMP，它们以非常有效的方式实现了各种各样的操作，并在汇编中进行了优化，仅用于此目的。

于 2010-01-23T23:28:48.177 回答