public class Exp {
  public static long expRapide(long x,long n) {
    System.out.println("expRapide("+x+","+n+")");
    if (n==0) return 1;
    if (n==1) return x;
    long r = expRapide(x,n/2);
    r = r*r;
    if (n%2==0) {
      return r;
    } else {
      return x*r;
    }           
  }
  public static long expRapide2(long x,long n) {
    if (n==0) return 1;
    if (n==1) return x;
    if (n%2==0) return expRapide2(x*x,n/2);
    else return x*expRapide2(x*x,n/2);
  }
  public static long expRapideAccumulee(long x,long n,long e) {
    if (n==0) return e;
    if (n==1) return x*e;
    if (n%2==0) return expRapideAccumulee(x*x,n/2,e);
    else return expRapideAccumulee(x*x,n/2,x*e);
  }
  public static void main(String []a) {
    System.out.println("2^20="+expRapide(2,20));
    System.out.println("2^20="+expRapideAccumulee(2,20,1));    
  }
}