Implement a power function
- Loop through the number of times the exponent, and during each iteration multiply the base
If our exponent is 10,000 then our loop has to run 10,000 times. But we can optimize this logic to use only log2(10,000) ~ 14 times by using the binary form of the exponent.
- If exponent’s last binary digit is one then multiply the result with base
- Divide the exponent by 2 by doing one left shift
- Multiply base with itself