Yuhang He's Blog

Some birds are not meant to be caged, their feathers are just too bright.

Fast reimplementation of pow( double x, int n)

Is there any fast implementation of $x^n$ in addition to the C++ function pow()?. The answer is yes! Here we talk about three reimplementation of this function.

  1. Intuitive Implementation:The intuitive implementation is that $x^n=x\cdot x \cdots x$, it can be implemented in a recursive style, note the case $n<0$.
1
2
3
4
5
6
7
double pow_new(double x, int n){
   if(n==0)
     return 1.0;
   if(n<0)
     return 1.0/pow_new(x,-n);
   return x*pow_new(x,n-1);
}
  1. Recursive implementation with O(logn) complexity: Note that $x^n=x^{[\frac{n}{2}]}\cdot x^{n−[\frac{n}{2}]}$, this leads to another version if we consider $x^n=(x^{[\frac{n}{2}]})^2⋅{x}$, where ${x}$ is an indicator function,${x}=1$ if $n$ is divisible by 2, otherwise ${x}=x$
1
2
3
4
5
6
7
8
9
10
11
double pow_new(double x, int n){
    if(n==0)
      return 1.0;
    if(n<0)
      return 1.0/pow_new(x,-n);
    double half = pow_new(x,n>>1);
    if(n%2==0)
      return half*half;
    else
      return half*half*x;
}

note that $n$ changes its value at every recursion. For example, if $n=5$, $n \ll 1 = 2$.

  1. Another fast implementation: Let’s consider the binary representation of $n$. For example, if $n$ is $10001011$, it can be represented as n = 10000000 + 00001000 + 000000010 + 00000001, then $x^n=x^{(1+2+8+128)}=x^1 \cdot x^2 \cdot x^8 \cdot x^{128}$. Thus, we don’t need to loop $n$ times to calculate $x^n$. To speed up, we loop through each non-zero bit, if the $i$-th bit is 1, then we add $x(1 \ll i)$ to the result. Since $( 1 \ll i )$ is a power of 2, $x(1 \ll (i+1))= square(x(1 \ll i))$. The loop executes for a maximum of log(n) times.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
double pow_new(double x, int n)
{
   if(n==0)
     return 1.0;
   if(n<0)
     return 1.0 / pow_new(x,-n);
   double pow_result = 1.0 ;
   for(; n>0; x *= x, n>>=1)
   {
     if(n&1>0)
       pow_result *= x;
   }
   return pow_result;
}

Note that $n&1$ indicates whether $n$ is an odd number or even number. Here if( n&1 >0 ) decides $n$ must be an odd number, the right-most binary digit must be 1. Whenever $n$ moves right for one step, x must multiply itself.