In this post I will implement basic algorithm to raise floating point number (also known as base) to integer power (also known as exponent). In academic world this process usually referred as Exponentiation. The most naïve implementation is based on the definition of xy, i.e. repetitive y-time multiplication of x.

Complexity: O(n).

This implementation can be optimized by using following exponentiation properties:

  • bm = b · bm-1
  • bm+n = bm · bn
  • bm·n = (bm)n In other words, given 27 we can calculate the result as follows:

27 = 2 · 26 = 2 · 22+4 = 2 · 22 · 24 = 2 · 22 · 22·2 = 2 · 22 · (22)2

As you can see, instead of 7 iterations now we have only 3.

Complexity: O(log n).