#include <cassert>
#include <climits>
#include <iostream>

// Recursive exponentiation by squaring
//
// Previously, we saw two ways to calculate a
// number raised to a non-negative integer power:
//
// 1. Repeated multiplication.
//
// 2. Exponentiation by squaring, using the bits
//    of the exponent.
//
// The second approach is much more efficient
// for large exponents.
//
// We can implement exponentiation by squaring
// recursively as well.
//
//
//
// Suppose we want to calculate:
//
//     x^m.
//
// If m is even, write:
//
//     m = 2k.
//
// Then:
//
//     x^m = x^(2k)
//         = (x^k)^2.
//
// If m is odd, write:
//
//     m = 2k + 1.
//
// Then:
//
//     x^m = x^(2k + 1)
//         = x*(x^k)^2.
//
// In both cases, we need only calculate:
//
//     x^(m/2)
//
// once, using integer division.
//
// We then square that result and, if m is odd,
// multiply by x one additional time.
//
//
//
// The trivial case
//
// Recall that:
//
//     x^0 = 1
//
// including when x is zero, using the usual
// programming convention that 0^0 evaluates
// to 1.
//
// Thus, the trivial case is:
//
//     m == 0.
//
//
//
// Negative exponents
//
// For a nonzero real number x:
//
//     x^(-m) = (1/x)^m.
//
// Thus, if the exponent is negative, we can
// recursively calculate a positive power
// of the reciprocal.
//
// There is, however, one subtle problem.
//
// The smallest possible value of a signed
// integer type has no corresponding positive
// value of the same type.
//
// For example, if long is a 64-bit signed
// integer:
//
//     LONG_MIN = -9223372036854775808
//
// but:
//
//     LONG_MAX =  9223372036854775807.
//
// Consequently, the expression:
//
//     -LONG_MIN
//
// cannot be represented by a long.
//
// We must avoid directly negating the most
// negative exponent.
//
//
//
// Your task
//
// Implement the following two overloads:
//
//     long pow( long, unsigned long );
//
//     double pow( double, long );
//
// The first calculates a non-negative integer
// power of an integer.
//
// The second calculates an integer power of
// a real number, including negative exponents.
//
//
//
// For the integer overload, assume the
// mathematical result fits in a long.
//
// Signed integer overflow is undefined behavior
// in C++.
//
// For the real overload, remember that:
//
//     0 raised to a negative power
//
// is undefined.


// Function declarations
int main();

long pow(
    long          const x,
    unsigned long const m
);

double pow(
    double const x,
    long   const m
);


// Function definitions
int main() {
    // Integer powers.
    //
    // The largest exponent used here is 19.
    //
    // (-3)^19 = -1162261467,
    //
    // which fits in a 32-bit signed long.

    for ( unsigned long m{ 0 }; m <= 19; ++m ) {
        std::cout << "(-3)^" << m << " = "
                  << pow( -3L, m )
                  << std::endl;
    }

    std::cout << std::endl;


    // Real powers, including negative exponents.

    for ( long m{ -10 }; m <= 10; ++m ) {
        std::cout << "(-1.003)^" << m << " = "
                  << pow( -1.003, m )
                  << std::endl;
    }

    std::cout << std::endl;


    // Test the trivial cases.

    assert( pow( 0L, 0UL ) == 1L );
    assert( pow( 0L, 5UL ) == 0L );
    assert( pow( 7L, 0UL ) == 1L );
    assert( pow( 7L, 1UL ) == 7L );

    assert( pow( 2L, 10UL ) == 1024L );
    assert( pow( -2L, 5UL ) == -32L );
    assert( pow( -2L, 6UL ) == 64L );

    assert( pow( 2.0, 0L ) == 1.0 );
    assert( pow( 2.0, 10L ) == 1024.0 );
    assert( pow( 2.0, -3L ) == 0.125 );

    // Test the most negative possible exponent.
    //
    // For x = -1, the answer is exactly 1
    // because LONG_MIN is even.

    assert( pow( -1.0, LONG_MIN ) == 1.0 );

    return 0;
}


// Your implementation of the integer overload.

long pow(
    long          const x,
    unsigned long const m
) {
    return 1;
}


// Your implementation of the real overload.

double pow(
    double const x,
    long   const m
) {
    return 1.0;
}














































// Hint 1
//
// Start with the trivial case:
//
//     m == 0.
//
// What should the function return?
//
//
//
// For a positive exponent, calculate:
//
//     result = pow( x, m/2 ).
//
// Then:
//
//     if m is even:
//
//         return result*result;
//
//     otherwise:
//
//         return x*result*result;
//
//
//
// IMPORTANT:
//
// Do NOT write:
//
//     return pow( x, m/2 )*pow( x, m/2 );
//
// That makes TWO recursive calls for the same
// subproblem.
//
// Instead, calculate the recursive result once:
//
//     long const result{ pow( x, m/2 ) };
//
// and reuse it.
//
// The same principle applies to the double
// overload.














































// Hint 2
//
// For the double overload, the negative-exponent
// case requires additional care.
//
// We would like to write:
//
//     return pow( 1.0/x, -m );
//
// But this is unsafe when:
//
//     m == LONG_MIN.
//
// Why?
//
// Because -LONG_MIN cannot be represented
// by a long.
//
//
//
// Instead, observe:
//
//     x^m = (1/x)*x^(m + 1)
//
// for every negative integer m.
//
// The exponent:
//
//     m + 1
//
// can always be safely negated when m is negative.
//
// Therefore:
//
//     x^m = (1/x)*(1/x)^(-(m + 1)).
//
//
//
// This gives us a safe recursive expression:
//
//     double const reciprocal{ 1.0/x };
//
//     return reciprocal
//          * pow( reciprocal, -(m + 1) );
//
// Notice that:
//
//     -(m + 1)
//
// is non-negative and fits in a long.
//
//
//
// You must also ensure:
//
//     x != 0.0
//
// before calculating its reciprocal.














































// Here is one solution:

/*
long pow(
    long          const x,
    unsigned long const m
) {
    if ( m == 0 ) {
        return 1L;
    } else {
        long const result{
            pow( x, m/2 )
        };

        if ( m%2 == 0 ) {
            return result*result;
        } else {
            return x*result*result;
        }
    }
}


double pow(
    double const x,
    long   const m
) {
    if ( m == 0 ) {
        return 1.0;
    } else if ( m < 0 ) {
        assert( x != 0.0 );

        double const reciprocal{ 1.0/x };

        return reciprocal
             * pow( reciprocal, -(m + 1) );
    } else {
        double const result{
            pow( x, m/2 )
        };

        if ( m%2 == 0 ) {
            return result*result;
        } else {
            return x*result*result;
        }
    }
}
*/












































// Understanding the recursion
//
// Consider:
//
//     pow( 3, 13 ).
//
// Since 13 is odd:
//
//     3^13 = 3*(3^6)^2.
//
// We therefore need:
//
//     pow( 3, 6 ).
//
// Since 6 is even:
//
//     3^6 = (3^3)^2.
//
// We therefore need:
//
//     pow( 3, 3 ).
//
// Since 3 is odd:
//
//     3^3 = 3*(3^1)^2.
//
// We therefore need:
//
//     pow( 3, 1 ).
//
// Since 1 is odd:
//
//     3^1 = 3*(3^0)^2.
//
// Finally:
//
//     pow( 3, 0 ) = 1.
//
//
//
// The recursive calls are:
//
//     pow( 3, 13 )
//         |
//     pow( 3, 6 )
//         |
//     pow( 3, 3 )
//         |
//     pow( 3, 1 )
//         |
//     pow( 3, 0 )
//
//
//
// The results are then calculated while
// the recursive calls return:
//
//     pow( 3, 0 ) = 1
//
//     pow( 3, 1 ) = 3*1*1
//                 = 3
//
//     pow( 3, 3 ) = 3*3*3
//                 = 27
//
//     pow( 3, 6 ) = 27*27
//                 = 729
//
//     pow( 3, 13 ) = 3*729*729
//                  = 1594323.
//
//
//
// How many recursive calls?
//
// Let C(m) count the calls made by the
// non-negative-exponent algorithm.
//
// We have:
//
//     C(0) = 1.
//
// For m > 0:
//
//     C(m) = C(floor(m/2)) + 1.
//
// This is the same recurrence we previously
// studied when analyzing binary search.
//
// Its exact solution for m > 0 is:
//
//     C(m) = floor(log_2(m)) + 2.
//
// The additional call is the final call
// with exponent zero.
//
// For example:
//
//     m = 13.
//
// The exponents are:
//
//     13, 6, 3, 1, 0.
//
// Thus:
//
//     C(13) = 5.
//
//
//
// Runtime
//
// Repeated multiplication requires:
//
//     Theta(m)
//
// multiplications to calculate x^m.
//
// Recursive exponentiation by squaring requires:
//
//     Theta(log(m))
//
// operations for m > 1.
//
// This is a substantial improvement.
//
//
//
// Why must we calculate the recursive result
// only once?
//
// Suppose we write:
//
//     return pow( x, m/2 )*pow( x, m/2 );
//
// for an even exponent.
//
// Now the recurrence for the number of calls is:
//
//     C(m) = 2*C(floor(m/2)) + 1.
//
// For powers of two, this produces a number
// of calls proportional to m.
//
// Thus, duplicating the recursive call destroys
// the logarithmic-time advantage.
//
//
//
// Space
//
// The maximum recursion depth is:
//
//     Theta(log(m))
//
// for a positive exponent.
//
// Every recursive call requires a stack frame.
//
// Consequently, the auxiliary space requirement
// is:
//
//     Theta(log(m)).
//
// An iterative implementation of exponentiation
// by squaring can perform the same calculation
// using:
//
//     Theta(1)
//
// auxiliary space.
//
// Both versions have logarithmic runtime.
//
//
//
// Integer overflow
//
// The integer overload returns a long.
//
// This type can represent only a finite range
// of integer values.
//
// Even when x and m are individually valid,
// the mathematical result x^m may not fit
// in a long.
//
// In C++, signed integer overflow is undefined
// behavior.
//
// The caller must therefore ensure that the
// result and intermediate products are
// representable.
//
//
//
// Floating-point limitations
//
// The double overload supports negative
// exponents, but it does not provide exact
// real arithmetic.
//
// For example:
//
//     pow( 1.003, 1000000 )
//
// may overflow the available floating-point
// range.
//
// Similarly, a very small result may underflow
// to zero.
//
// Rounding errors can also accumulate.
//
// These limitations are properties of
// floating-point arithmetic, not of recursion.
//
//
//
// Questions
//
// 1. What is the trivial case for both
//    overloads?
//
// 2. Why do we divide the exponent by two?
//
// 3. How do we handle an odd exponent?
//
// 4. Why must the recursive result be
//    calculated only once?
//
// 5. Trace the calls made by:
//
//        pow( 2, 11 ).
//
// 6. How many calls are made by:
//
//        pow( 2, 1024 )?
//
// 7. Why is the runtime logarithmic in
//    the exponent?
//
// 8. Why does the recursive algorithm use
//    more auxiliary space than the iterative
//    version?
//
// 9. Why can we not safely calculate:
//
//        -LONG_MIN?
//
// 10. How does the negative-exponent branch
//     avoid this problem?
//
// 11. Why is:
//
//        pow( 0.0, -3 )
//
//     undefined?
//
// 12. What happens if the mathematical result
//     does not fit in a long?
//
//
//
// The central idea
//
// Instead of reducing the exponent by one:
//
//     x^m = x*x^(m - 1),
//
// reduce it by approximately half:
//
//     x^m = (x^(m/2))^2
//
// for even m, with one additional factor
// of x for odd m.
//
// This changes the recursion depth from
// linear to logarithmic.
//
// The same divide-by-two strategy appears
// in binary search, fast integer algorithms,
// and many divide-and-conquer algorithms.