Binary Exponentiation

Algorithm description

Finding \(a^n\) involves doing \(n\) multiplications of \(a\), the same operation can be done in \(O(log(n))\) multiplications

For any number \(a\) raised to an even power:

\[ a^n = (a^{n/2})^2 = a^{n/2} \cdot a^{n/2} \]

For any number \(a\) rasied to an odd power:

\[ a^n = a^{n - 1} \cdot a \]

Implementation

Time complexity: \(O(log(n))\)

/**
 * Computes
 *
 *    a^k
 *
 * Given the following facts:
 *
 * - if `k` is even then a^(2k) = (a^k)^2
 * - if `k` is odd then a^(2k + 1) = (a^k)^2 * a
 */
int logarithmic_exponentiation(int a, int k) {
  if (k == 0) {
    // a^0 = 1
    return 1;
  }
  if (k % 2 == 1) {
    return binary_exponentiation(a, k - 1) * a;
  } else {
    int t = binary_exponentiation(a, k / 2);
    return t * t;
  }
}

// iterative implementation
int binary_exponentiation(int a, int k) {
  int x = 1;
  while (k) {
    // analyze the i-th bit of the binary representation of k
    if (k & 1) {
      x *= a;
    }
    a *= a;
    k >>= 1;
  }
  return x;
}