#include <iostream>
using namespace std;

// illustrates recursion and the exponentiation operator

int PowerSlowIter (int base, int expo)
// pre:  expo >= 0
// post: returns base^expo (base to the power expo)
{
    int result = 1;

    for (int k = 0; k < expo; k++)
    {
        result *= base;
    }

    return result;
}

int PowerSlowRec (int base, int expo)
// pre:  expo >= 0
// post: returns base^expo (base to the power expo)
{
    if (0 == expo)
    {
        return 1;
    }
    else
    {
        return base * PowerSlowRec(base, expo-1);
    }
}


int PowerFastIter (int base, int expo)
// pre:  expo >= 0
// post: returns base^expo (base to the power expo)
{
    if (0 == expo)
    {
        return 1;
    }
    else
    {
        int result = base;

        int k = 2;
        while (k <= expo)
        {
            result *= result;
            k *= 2;
        }

        if (k != expo)
        {
            k /= 2;
            while (k < expo)
            {
                result *= base;
                k++;
            }
        }

        return result;
    }
}

int PowerFastRec (int base, int expo)
// pre:  expo >= 0
// post: returns base^expo (base to the power expo)
{
    if (0 == expo)
    {
        return 1;
    }
    else
    {
        int semi = PowerFastRec(base, expo/2);
        if (expo % 2 == 0)
        {
            return semi * semi;
        }
        else
        {
            return base * semi * semi;
        }       
    }
}


int main ()
{
    int base, expo;
    cout << "enter base and exponent: ";
    cin  >> base >> expo;

    int result;
    result = PowerSlowIter(base, expo);
    cout << base << " ** " << expo << " = " << result << endl;
    result = PowerSlowRec(base, expo);
    cout << base << " ** " << expo << " = " << result << endl;
    result = PowerFastIter(base, expo);
    cout << base << " ** " << expo << " = " << result << endl;
    result = PowerFastRec(base, expo);
    cout << base << " ** " << expo << " = " << result << endl;

    return 0;
}