代码之家 › 专栏 › 技术社区 › telliott99

蟒蛇:有多快?

computation largenumber python

6

telliott99 · 技术社区 · 15 年前

模块中使用的Mersenne捻线器的周期 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

问题是:这实际上是如何做到的?

我是不是太天真了?我发现pythonshell在瞬间生成了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 回复 | 直到 15 年前

1

4

Thorsten S. 15 年前

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

作为附加信息:十进制的转换通常通过一种征服和除法算法来实现,该算法将数字依次除以十的幂。如你所见, 实际转换速度慢了50万倍。

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

示例:10^345

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

C C C C C C b*10

(可进一步优化:参见Knuth,半数值算法)

编辑:乘法的精确实现取决于:除了正常的学校乘法Karatsuba外,Tom Cooke和Schoenhagen Strasse(FFT)乘法是

2

6

clee nortron 15 年前

我不想在你的阅兵式上泼冷水,但它这么快的原因是数学模块实际上并没有用Python实现。

Python支持加载导出Python API的共享库,但这些库是用其他语言实现的。math.so,这提供了您从中获得的模块 import math ,正好是其中之一(随机性也是如此)。

3

5

mthurlin 15 年前

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

4

0

Jakob Borg 15 年前

事实上 用Python实现,但考虑到这基本上是原语乘法和对数,即使在相当大的数字上它也相当快,我并不感到惊讶。

有任意精度的数学库,例如 GMP