Python: how fast?

Question

The Mersenne Twister period used in the random module, (I said) 2 ** 19937 - 1. As a binary number, that is 19937 '1 in a row (if I'm not mistaken), Python converts it to decimal pretty quickly:

 $ 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 

I assume the second version requires conversion?

And this is not just binary. It is also fast. (Instead of showing numbers, I show the length of the decimal number converted to a 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 

Timing:

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

Question: how is this done?

Am I just naive to be impressed? I find a look at the Python shell creating some 5,000 or so places in an instant, truly breathtaking.

Edit:

Additional timings offered by @dalke and @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 

So it seems to me that result = 0; result += 2**19937 result = 0; result += 2**19937 probably forces the conversion.

Answer 1

Python converts it to decimal fast wired.

I do not know Python, but no, this does not need to be done. 2 ^ 19937 no calculations are needed, it's just a binary shift ("<") from 19937, so it's really fast. Only if you print it in decimal format, the actual conversion is necessary and it is much slower.

EDIT: The exponentiality can be the same as a shift (= moving a point) if the base of the numbers is identical to the base of the exponentials.

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

You see that exponential 10 with exponent n just shifts the number. Now, computers mainly use internal base 2 (bit), so computing 2 ^ 19937 sets the bit at position 19937 (counting bit positions from zero).
As additional information: decimal conversion is usually implemented by the subjugation and division algorithm, which sequentially divides the number by ten. As you can see, the actual conversion is slower in one and a half million.

The second example is more interesting: since you are calculating m ^ n with large integers m, n, the fastest way is to multiply it sequentially and save temporary results.

Example: 10 ^ 345

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

result = dccccccccbb * 10

(May be further optimized: see Knuth, Seminumerical Algorithms)

So, you only need long multiplications, and they can be calculated quite efficiently.

EDIT: The exact implementation of the multiplication depends: besides the usual multiplication of the Karatsub school, Tom-Cook and Schoenhagen-Strasse (FFT) multiplication b.

Answer 2

I hate rain in your parade, but the reason is so fast because the math module is not actually implemented in Python.

Python supports loading shared libraries that export Python APIs but are implemented in other languages. math.so, which provides the module that you get from import math , turns out to be one of them (and so _random.so).

Answer 3

When compiled into byte code, constant expressions, such as 2**19937 , will be optimized to one constant:

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

Consider instead:

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

Answer 4

I don't know much about how this is implemented in Python, but given that it is mostly primitive multiplication and logarithms, I'm not very surprised that it is fast enough even on fairly large quantities.

There are mathematical libraries of precision accuracy, such as GMP , which carry out very diverse operations in a very efficient way, optimized in the assembly, just for this purpose.