• 0

Implement a power function

Naive logic:

  • 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.

Optimized logic:

  • 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

Solution :