#include <iostream>

/***************************************************
 * Efficient calculation of integer powers
 *
 * Suppose we want to calculate
 *
 *     n^m
 *
 * where m is a non-negative integer.
 *
 * We have already written a function that calculates
 * this using a loop:
 *
 *     long product{ 1 };
 *
 *     for ( unsigned long k{ 0 }; k < m; ++k ) {
 *         product *= n;
 *     }
 *
 * This requires m multiplications.
 *
 * We can calculate the same result much more
 * efficiently by using the binary representation of
 * the exponent. This algorithm is called
 * exponentiation by squaring.
 *
 *
 * USING THE BINARY REPRESENTATION
 *
 * Recall that
 *
 *     n^(a + b) = n^a * n^b.
 *
 * Suppose the exponent is 42. In binary,
 *
 *     42 = 101010
 *
 * and therefore
 *
 *     42 = 32 + 8 + 2.
 *
 * Consequently,
 *
 *     n^42 = n^32 * n^8 * n^2.
 *
 * We can generate all the powers that we might need
 * by repeatedly squaring:
 *
 *     n
 *     n^2
 *     n^4
 *     n^8
 *     n^16
 *     n^32
 *     ...
 *
 * Each squaring requires only one multiplication.
 *
 *
 * USING A BIT MASK
 *
 * At the same time, consider the masks
 *
 *     000001
 *     000010
 *     000100
 *     001000
 *     010000
 *     100000
 *
 * These correspond to the powers
 *
 *     1, 2, 4, 8, 16, 32.
 *
 * We can therefore examine each bit in the exponent
 * m. If the corresponding bit is 1, we multiply the
 * appropriate power of n into our result.
 *
 * For example,
 *
 *            42 = 101010
 *
 * so we use
 *
 *                 ^   ^ ^
 *                32   8 2
 *
 * and calculate
 *
 *     n^42 = n^32 * n^8 * n^2.
 *
 *
 * WHY IS THIS FASTER?
 *
 * Consider calculating
 *
 *     3^40.
 *
 * The simple algorithm calculates
 *
 *     1 * 3 * 3 * ... * 3
 *
 * and therefore requires 40 multiplications.
 *
 * The binary representation of 40 is
 *
 *     40 = 101000
 *
 * or
 *
 *     40 = 32 + 8.
 *
 * We obtain the necessary powers by successively
 * squaring:
 *
 *     3
 *     3^2
 *     3^4
 *     3^8
 *     3^16
 *     3^32
 *
 * Obtaining 3^32 requires five squarings.
 *
 * We then need
 *
 *     3^40 = 3^32 * 3^8,
 *
 * requiring one additional multiplication.
 *
 * Thus, if we avoid multiplying the initial 1 by a
 * selected power, 3^40 can be calculated using six
 * multiplications rather than 40.
 *
 * More generally, the simple algorithm requires a
 * number of multiplications proportional to m,
 * whereas exponentiation by squaring requires a
 * number proportional to the number of bits in m.
 *
 *
 * NEGATIVE EXPONENTS
 *
 * An integer result cannot generally represent a
 * negative power. For example,
 *
 *     3^(-2) = 1/9.
 *
 * Consequently, our integer version accepts only a
 * non-negative exponent.
 *
 * Our floating-point version can also calculate
 * negative powers because
 *
 *     x^(-m) = (1/x)^m.
 *
 * For example,
 *
 *     2^(-3)
 *         = (1/2)^3
 *         = 1/8.
 ***************************************************/

// Function declarations
int main();
long pow( long n, unsigned long m );
double pow( double x, long m );

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

    std::cout << std::endl;

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

    return 0;
}

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

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




























// Hint:
//
// Start with
//
//     product         = 1
//     n_to_power_of_2 = n
//     mask            = 1
//
// The mask represents the exponent associated with
// n_to_power_of_2:
//
//     mask        n_to_power_of_2
//
//       1               n
//       2              n^2
//       4              n^4
//       8              n^8
//      16              n^16
//      32              n^32
//      ...
//
// With each iteration:
//   - determine whether the corresponding bit of m
//     is 1,
//   - if it is, multiply n_to_power_of_2 into product,
//   - square n_to_power_of_2, and
//   - shift mask one bit to the left.





























// Another hint:
//
//     n *= n;       // Square n.
//     mask <<= 1;   // Multiply the mask by 2.











































// Answer to the question:
//
// In calculating 3^40, the simple implementation
// requires 40 multiplications.
//
// Since
//
//     40 = 101000
//
// we need the powers
//
//     3, 3^2, 3^4, 3^8, 3^16, 3^32.
//
// These require five squarings.
//
// Since
//
//     3^40 = 3^32 * 3^8,
//
// one additional multiplication gives the result.
//
// Thus, 3^40 can be calculated using six
// multiplications instead of 40.


// Here is one solution:

/*
long pow( long n, unsigned long m ) {
    long product{ 1 };
    long n_to_power_of_2{ n };
    unsigned long mask{ 1 };

    while ( mask <= m ) {
        if ( (m & mask) != 0 ) {
            product *= n_to_power_of_2;
        }

        n_to_power_of_2 *= n_to_power_of_2;
        mask <<= 1;
    }

    return product;
}

double pow( double x, long m ) {
    if ( m < 0 ) {
        x = 1.0/x;
        m = -m;
    }

    double product{ 1.0 };
    double x_to_power_of_2{ x };
    unsigned long mask{ 1 };

    while ( mask <= static_cast<unsigned long>( m ) ) {
        if ( (static_cast<unsigned long>( m ) & mask) != 0 ) {
            product *= x_to_power_of_2;
        }

        x_to_power_of_2 *= x_to_power_of_2;
        mask <<= 1;
    }

    return product;
}
*/