快速幂算法

快速幂算法，可以将时间复杂度从O（N）降为O（log2N）。

比如要算2^n (n>0)，最简单的方法是：

int result = 0;
for (int i = 0; i < n; i++)
    result *= 2;

时间复杂度是O（N）。

当n为偶数：
2^n = 2^(n/2) * 2^(n/2)
2^(n/2) = 2^(n/4) * 2^(n/4)
2^(n/4) = 2^(n/8) * 2^(n/8)
......

当n为奇数：
2^n = 2^(n/2) * 2^(n/2) * 2
2^(n/2) = 2^(n/4) * 2^(n/4)
2^(n/4) = 2^(n/8) * 2^(n/8)

推广为：
base^n = base^(n/2) * base^(n/2)； 
base^n = base * base^((n-1)/2) * base^((n-1)/2)；
......

这样分解下去，就可以把时间复杂度降为O(log2N)。

现在可以用这个方法来实现pow函数:

double tiny_pow(double base, int n) 
{
     // 0的0次方极限趋近于1. 0^-1，0^-2会引起CPU异常，所以不作处理
    if (equal(base, 0.0) && n == 0)
        return 0.0;

    unsigned int absN = ( n > 0 ? (unsigned int)n : abs(n) );
    
    double result = powWithUnsignedN(base, absN); 
    if (n < 0)
        result = 1.0 / result;
    
    return result;
}

double powWithUnsignedN(double base, unsigned int n)
{
    if (n == 0)  return 1;

    if (n == 1)  return base;  // 也是递归开始回溯的地方

    double result = powWithUnsignedN(base, n >> 1);
    result *= result ;
     
    if (n & 1)      // n为奇数
        result *= base;
    
    return result ; 
}

bool equal(double num1, double num2) 
{        
    // |num1 - num2| < 0.0000001
    if (-0.0000001 < (num1 - num2) && (num1 - num2) < 0.0000001) 
        return true;
    else
        return false;
}