import java.io.*;

public class Pow
{
    // Compute x**n 
    public static int pow(int x, int n) {
	int p = 1;
	int y = x;
	while (n > 0) {
	//Loop Invariant: if we are at the m-th iteration 
	//(with initially m=0), n is the initial n divided
	//by 2**m, y is x**2**m, and p is x raised to the
	//sum of all the sum of all the powers of 2 with
	//degree at most m that appear in the binary expansion of 
	//the original n!!!!
	//Question: what is the complexity of this program
	//as a function of n?
	    if (n%2 == 1)
		p *= y;
	    n = n/2;
	    y = y*y;
	}
	return p;
    }

    // Compute x**n recursively
    public static int powR(int x, int n) {
	if (n == 0)
	    return 1;
	int y = powR(x*x, n/2);
	if (n % 2 == 1)
	    y = y*x;
	return y;
    }

    public static void main(String[] args) throws IOException {
	BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	System.out.print("Enter base: ");
	int x = Integer.parseInt(rd.readLine().trim());
	System.out.print("Enter exponent: ");
	int n = Integer.parseInt(rd.readLine().trim());
	System.out.println("The result of pow is " + pow(x, n));
	System.out.println("The result of powR is " + powR(x, n));
    }
}