I was trying to implement the Miller-Rabin algorithm for one of my home-works, in Python. I had already done this in C++ to solve PON, but I wanted to try out Python, and see how fast I can get it to. I wrote a function to do $a\^b$ mod $n $ which used repeated squaring to get the result. However, the implementation wasn’t fast enough. Dhruv suggested that I profile the code.
Here is how you profile a python script:
python -m cProfile script.py
And this is what I came to know
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Note how the
fastModularExp() function took a staggering 16 seconds. Now we came to know that the builtin pow function in Python already does fast modular exponentiation. And since it is a part of a C library, it is quite fast. After doing this, I submitted it as a solution for PON and got accepted with 0.35 seconds, which was faster than my 0.90 submission with C++ :-)