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 valeurPartielle) {
    if (n==0) return valeurPartielle;
    if (n==1) return x*valeurPartielle;
    if (n%2==0) return expRapideAccumulee(x*x,n/2,valeurPartielle);
    else return expRapideAccumulee(x*x,n/2,x*valeurPartielle);
  }
  public static long expRapideAccumuleeRecEliminee(long x,long n,long valeurPartielle) {
    while (true) {
      if (n==0) return valeurPartielle;
      if (n==1) return x*valeurPartielle;
      if (n%2==0) {
        x = x*x;
        n = n/2;
      } else {
        valeurPartielle = x*valeurPartielle;
        x = x*x;
        n = n/2;
      }
    }
  }
  public static void main(String []a) {
    System.out.println("2^20="+expRapide(2,20));
    System.out.println("2^20="+expRapideAccumulee(2,20,1));    
  }
}