In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add.

The traditional power function we write:

int pow(int x, int n) {
  int res = 1;
  for (int i=0; i<n; ++i)
    res *= x;
  return res;
}

The fast_pow:

int fast_pow(int x, int n) {
  int res = 1;
  while(n) {
    if (n%2==1) res *= x;
    x *= x;
    n /= 2;
  }
  return res;
}

It can also be written in this way (which looks better):

int fast_pow(int x, int n) {
  int res = 1;
  while(n) {
    if (n&1) res *= x;
    x *= x;
    n >>= 1;
  }
  return res;
}

We have HDU 1061 to test this code: