I am a python newbie. I am looking to compute (a ** b) % 10 in the most efficient way possible (i.e. simplifying the power part). I have found one way to do this: ((a % 10) ** b) % 10. My question is, are there more efficient ways to do this? This problem is an extension of a CodeFights task. The original problem accepted (a ** b) % 10.
Since the numbers mod 10 form a ring, you can compute the residue mod 10 at every intermediate value without influencing the result.
There is a O(log b) step algorithm called Square-and-multiply that can drastically speed up your computations.
The basic idea is that for even b, we can just square the argument
and divide the exponent by 2 without changing the result.
For odd b, we extract one power of a (or our current argument) and proceed like in the even case (squaring and halving).
So putting this together, if you implement the Square-and-multiply algorithm and compute the residue mod 10 after every step, you will have a nice and efficient way to compute your last digit.