# 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. 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$

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.

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.