Algorithm description

Finding an 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:

an=(an/2)2=an/2an/2

For any number a rasied to an odd power:

an=an1a

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;
}