##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
(Computing 2^10)
Compute 2^10. Instead of 10 multiplications, do this: 2^10 = (2^5)^2. Then 2^5 = 2 × (2^4). Then 2^4 = (2^2)^2. Then 2^2 = (2^1)^2. Then 2^1 = 2.
Work backward: 2^1 = 2. 2^2 = 4. 2^4 = 16. 2^5 = 2 × 16 = 32. 2^10 = 32^2 = 1024. Only 5 operations instead of 10.
For large n, this saves massive time. And taking mod after each step prevents overflow.
