// Beregning av X^n med dynamisk programmering

// Ide: X^7 = X^4 * X^2 * X^1
//      X^9 = X^8 * X^1

public class Power {

long Pow[];

public Power(int n) {
   Pow = new long[n];
}

public long findPow(int x, int n) {
	Pow[1] = x;
	int i	= 1;
	int exp = 1;
	
	while (exp < n) {
		i++;
		exp = 2*exp;
		Pow[i] = Pow[i-1]*Pow[i-1];
	}

	// Finner x^n ved aa gaa baklengs

	int brukt = 0;
	long xn = 1;

	while (brukt < n) {
		if (brukt + exp <= n) {
			xn = xn * Pow[i];
			brukt = brukt + exp;
		}
		exp = exp/2;
		i--;
	}

	return xn;
}

// Rekursiv rutine:

public long findPowRec(long x, long n) {
	if (n == 0) return (long)1;
	if (n == x) return x;

	if (n%2==0)
		return findPowRec(x*x,n/2);
	else
		return findPowRec(x*x,n/2)*x;
}

public static void main(String[] args) {
   if (args.length != 2) {
      System.out.println("Usage: java Power n x\nReturns n^x");
      return;
   }

   Power p = new Power(Integer.parseInt(args[1]));
   System.out.println("Dynamisk programmering: " +
     p.findPow(Integer.parseInt(args[0]), Integer.parseInt(args[1]))
   );
   System.out.println("Rekursiv metode: " +
     p.findPowRec(Long.parseLong(args[0]), Long.parseLong(args[1]))
   );
   
}

}