public class Exp {
  public static long exp(long x,long n) {
    System.out.println("exp("+x+","+n+")");
    if (n==0) return 1;
    return x*exp(x,n-1);
  }
  public static long expRapide(long x,long n) {
    System.out.println("expRapide("+x+","+n+")");
    if (n==0) return 1;
    if (n%2==0) {
      long res = expRapide(x,n/2);
      return res*res;
    } else {
      long res = expRapide(x,n/2);
      return x*res*res;
    }
  }
  public static long expRapideAcc(long x,long n,long acc) {
    System.out.println("expRapideAcc("+x+","+n+","+acc+")");
    if (n==0) return acc;
    if (n%2==0) {
      return expRapideAcc(x*x,n/2,acc);
    } else {
      return expRapideAcc(x*x,n/2,x*acc);
    }
  }
  public static long expRapideAccIter(long x,long n,long acc) {
    System.out.println("expRapideAcc("+x+","+n+","+acc+")");
    while (n!=0) {
      if (n%2==0) {
        x = x*x;
        n = n/2;
      } else {
        acc = x*acc;
        x = x*x;
        n = n/2;
      }
    }
    return acc;
  }
  public static void main(String []a) {
    System.out.println(exp(4,11));
    System.out.println(expRapide(4,11));
    System.out.println(expRapideAcc(4,11,1));
    System.out.println(expRapideAccIter(4,11,1));
  }
}