2**32 being calculated multiple times

[Siddhesh-Agarwal]

What would you like to share?

In this file 2**32 is being calculated multiple times.

we can instead use a variable MOD = 1 << 32 and save lots of compute time.

Additional information

Bit shift is faster than multiplication in all languages.

[amirsoroush]

Yes it's faster in general. Here is a test with slightly modified expression:

from timeit import timeit

n = 1_000_000
print(timeit("2**x", setup="x=32", number=n))  # 0.18543391000093834
print(timeit("1<<x", setup="x=32", number=n))  # 0.03452191699943796

I intentionally did that to show the difference. Python does something called "constant folding". When the script is complied, both 2 ** 32 and 1 << 32(because they are constants) are replaced with 4294967296. So that was to prevent this.

To show constant folding in action:

from dis import dis

dis("2**32")
print("-----------------------------------")
dis("1<<32")

output:

  1           0 LOAD_CONST               0 (4294967296)
              2 RETURN_VALUE
-----------------------------------
  1           0 LOAD_CONST               0 (4294967296)
              2 RETURN_VALUE

[Siddhesh-Agarwal]

@amirsoroush In C++, the << operator is significantly much faster but that doesn't seem to be the case in (newer versions of) Python. As you said, the error is indeed negligible. Thanks for the clarification.

[amirsoroush]

@Siddhesh-Agarwal You're right, It's faster in Python too. Sorry if my first comment was not so informative. I updated it with more details.

[Siddhesh-Agarwal]

@amirsoroush Does it mean that I can go ahead and change it?

[amirsoroush]

@Siddhesh-Agarwal I'm afraid not. The runtime is going to be the same anyway. In compile time Python will calculate 2**32 and use the result instead. So no matter if that expression is inside a for loop, Python uses the result of that. If the module is being imported, Python creates a .pyc file and for further run, it won't even compile that module again. The compilation step is done every time the module is executed as the main module though.

[amirsoroush]

@cclauss May I ask your opinion on that?

[cclauss]

Given that the slower operation can be done 5 million times in one second, I think that the most important question should be "Which will be easier for the reader to understand?"

[Siddhesh-Agarwal]

Thanks for the clarity on the topic @amirsoroush and @cclauss.