// A faster integer power
// Include this in your main program
// Includes int pow(int,int) and int square(int)
#include <iostream.h>
int pow(int m, int n)// Given n and m returns m to the power n
	//Pre: n must be >= 0.
	//Post: Nothing global is changed
	//Returns: the product of n' ms
	//Exceptions: When n<0 it returns 0 and outputs an warning to cerr
	//Bugs: Does not handle overflow of large powers.
/*
-----ANALYSIS-----
Formulae
	pow(m, 0)=1;
	pow(m, 2*k) = pow(square(m), k)
	pow(m, 2*k+1)= m * pow(m,2*k)
Algorithm
   if n is negative
	report error and set p to 0
   else when n is >=0
	Repeatedly reduce the power until it becomes zero
		keeping track of the effect in p and m.
*/
{
	//uses
		int square(int);// returns square of argument
	//Local Data
	int p=1; //working storage for the power.

	if( n<0 )
	{
		cerr<< "In pow("<<m<<", "<<n<<"), n is negative"<<endl;
		p=0;
	}
	else // n>=0
	{
		while(n>0)  // here pow(m0,n0) is p * pow(m, n)
			    //	where m0 and n0 were the initial values of m,n.
		{ 	//n>0
			if( n % 2 == 0 )  // so that n is 2*k or equivalently
						// k is n/2.
			{
				m = square(m);
				n = n/2;
			}
			else // n is odd and 2*k+1
			{
				p = p * m;
				n--;
			}
		} // n==0
		  // So pow(m0,n0) is p*pow(m,0) is p.
	}

	return p;
}

int square(int m){return m*m;}

/* test harness
main()
{
	int m,n;
	cout <<"m n? "; cin >>m>>n;
	cout <<pow(m,n)<<endl;
}
*/