# Why is 2 * x * x faster than 2 * ( x * x ) in Python 3.x, for integers?

• A+
Category：Languages

The following Python 3.x integer multiplication takes on average between 1.66s and 1.77s:

``import time start_time = time.time() num = 0 for x in range(0, 10000000):     # num += 2 * (x * x)     num += 2 * x * x print("--- %s seconds ---" % (time.time() - start_time)) ``

if I replace `2 * x * x` with `2 *(x * x)`, it takes between `2.04` and `2.25`. How come?

On the other hand it is the opposite in Java: `2 * (x * x)` is faster in Java. Java test link: Why is 2 * (i * i) faster than 2 * i * i in Java?

I ran each version of the program 10 times, here are the results.

``   2 * x * x        |   2 * (x * x) --------------------------------------- 1.7717654705047607  | 2.0789272785186768 1.735931396484375   | 2.1166207790374756 1.7093875408172607  | 2.024367570877075 1.7004504203796387  | 2.047525405883789 1.6676218509674072  | 2.254328966140747 1.699510097503662   | 2.0949244499206543 1.6889283657073975  | 2.0841963291168213 1.7243537902832031  | 2.1290600299835205 1.712965488433838   | 2.1942825317382812 1.7622807025909424  | 2.1200053691864014 ``

First of all, note that we don't see the same thing in Python 2.x:

``>>> timeit("for i in range(1000): 2*i*i") 51.00784397125244 >>> timeit("for i in range(1000): 2*(i*i)") 50.48330092430115 ``

So this leads us to believe that this is due to how integers changed in Python 3: specifically, Python 3 uses `long` (arbitrarily large integers) everywhere.

For small enough integers (including the ones we're considering here), CPython actually just uses the O(N2) grade-school digit by digit multiplication algorithm (for larger integers it switches to the Karatsuba algorithm). You can see this yourself in the source.

The number of digits in `x*x` is roughly twice that of `2*x` or `x` (since log(x2) = 2 log(x)), so the square of the number of digits in `x*x` (recall that grade-school multiplication is quadratic) is 4 times that of `2*x` or `x` -- so it makes sense that `2*(x*x)` is the slower variant.

Note that a "digit" in this context is not a base-10 digit, but a 30-bit value (which are treated as single digits in CPython's implementation). Hence, for `x = 10000000`, `2*x*x` only requires single-digit multiplications whereas `2*(x*x)` requires a 2-digit multiplication (since `x*x` has 2 30-bit digits).

Here's a direct way to see this (Python 3):

``>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000) 5.796971936999967 >>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000) 4.3559221399999615 ``

Again, compare this to Python 2, which doesn't use arbitrary-length integers everywhere:

``>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000) 3.0912468433380127 >>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000) 3.1120400428771973 ``

(One interesting note: If you look at the source, you'll see that the algorithm actually has a special case for squaring numbers (which we're doing here), but even still this is not enough to overcome the fact that `2*(x*x)` just requires processing more digits.)