/**
 * http://en.wikipedia.org/wiki/Exponentiation_by_squaring
 *
 * pow uses typical divide conqure algorithm, it takes O(log n) time, but also
 *     O(log n) space; pow2 uese 2k-ary method, each time double the base and
 *     check if final result contains this part for multiplication, it also takes
 *     O(log n) time but only O(1) space
 * 
 * 2^15    = 2 * (2 * (2 * 2^2)^2)^2 
 *         = 2 * 2^2 * 2^4 * 2^8
 *
 * We can see this
 * for pow, it kind of go from low bit to high bit, then calculate from high bit
 *     back to low bit;
 * for pow2, it just calculate from low bit to high bit.
 */



double pow2(double x, int n) 
{
    if (n < 0) 
    {
        x = 1/x;
        n = -n;
    }
    double base = x;
    double result = 1;
    while(n) 
    {
        if (n&1)
        {
            result *= base;
        }

        base = base*base;
        n >>= 1;
    }

    return result;
}


/*
**  A typical divide conquer problem
*/

double pow(double x, int n)
{
    if(n == 0) return 1;
    if(n == 1) return x;

    bool negative = false;
    if(n < 0) 
    {
        negative = true;
        n = -n;
    }

    //apply divide conquer algorithm
    double r = pow(x, n/2);
    r = r*r;
    if ( n%2 != 0) r *= x;

    if (negative) r = 1/r;

    return r;
}

#include <stdio.h>

int main(int argc, char** argv)
{
    double base = 7.21;
    for (int i = 0; i < 21; ++i)
    {
        printf("%f, %d,  pow = %28.7f, pow2 = %28.7f\n", base, i, 
            pow(base, i),
            pow2(base, i));
    }
    // printf("pow(%f,%d) = %f\n", 0.0, 2, pow(0.0,2));
    return 0;
}