Python: Com que rapidez?

Question

O período do Mersenne Twister usado no módulo random é (me disseram) 2 ** 19937 - 1. Como um número binário, ou seja, de 19937 '1's seguidos (se não me engano). Python o converte para decimal bastante rápido:

$ 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

Eu acho que a segunda versão é a que requer conversão?

E não é apenas binário. Isso também é rápido. (Em vez de mostrar os números, mostro o comprimento do decimal convertido em uma string):

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

Cronometragem:

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

A questão é: como isso é realmente feito?

Sou ingênuo por ficar impressionado? Acho que a visão da concha Python gerando uma série de 5000 lugares em um instante verdadeiramente espetacular.

Editar:

Horários adicionais sugeridos por @dalke e @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

Então me parece como result = 0; result += 2**19937 Provavelmente força a conversão.

Answer 1

Python o converte para decimal bastante rápido.

Eu não conheço Python, mas não, não precisa fazer isso. 2^19937 Não precisa de cálculos, é simplesmente uma mudança binária ("<<") com 19937, por isso é muito rápido. Somente se você imprimir em decimal, a conversão real é necessária e isso é muito mais lento.

Editar: a exponenciação pode ser a mesma que a mudança (= mover o ponto) se a base de números for idêntica à base do expoente.

10^-1 = 0.1 10^0 = 1
10^1 = 10
10^2 = 100
10^3 = 1000
10^n = 1 (n zeros)

Você vê essa exponenciação de 10 com o expoente n simplesmente muda o número. Agora, os computadores usam principalmente a base interna 2 (bits); portanto, calcular 2^19937 está definindo um pouco na posição 19937 (contando posições de bits de zero).
Como informações adicionais: a conversão para decimal é normalmente implementada por um algoritmo de conquista e divisão que divide sucessivamente o número por poderes de dez. Como você vê, a conversão real é mais lenta por um fator de meio milhão.

O segundo exemplo é mais interessante: como você está computando M^n com grandes números inteiros m, a maneira mais rápida é multiplicando -o em sucessão e armazenar os resultados temporários.

Exemplo: 10^345

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

resultado = dccccccccbB*10

(Pode ser otimizado ainda mais: ver Knuth, algoritmos seminuméricos)

Portanto, você só precisa de multiplicações longas e elas podem ser calculadas de maneira bastante eficaz.

EDIT: A implementação exata da multiplicação depende: Além da multiplicação normal de multiplicação escolar, a multiplicação de Schoenhagen-Strasse (FFT) é usada.

Answer 2

Odeio chover em seu desfile, mas a razão pela qual é tão rápido é porque o módulo de matemática não é implementado em Python.

O Python suporta carregar bibliotecas compartilhadas que exportam APIs Python, mas são implementadas em outros idiomas. math.so, que fornece o módulo de que você obtém import math, por acaso é um desses (e também é _random.so).

Answer 3

Ao compilar em código de bytes, expressões constantes como 2**19937 será otimizado para uma única constante:

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

Considere em vez disso:

[~] python -m timeit 'x=2' 'x**19937'
1000 loops, best of 3: 210 usec per loop

Answer 4

Eu sei pouco ou nada sobre como isso é na realidade Implementado em Python, mas, como isso é basicamente multiplicação e logaritmos primitivos, não estou muito surpreso por ser razoavelmente rápido mesmo em números bastante grandes.

Existem bibliotecas de matemática de precisão arbitrária, como GMP que implementam uma ampla variedade de operações de uma maneira muito eficaz, otimizadas na montagem, para esse fim.