public class Exp {
  public static int compteur;
  public static int exp(int x,int n) {
    System.out.println("exp("+x+","+n+")");
    compteur++;
    if (n==0) return 1;
    return x*exp(x,n-1);
  }
  public static int compteur2;
  public static int expRapide(int x,int n) {
    compteur2++;
    if (n==0) return 1;
    if (n%2==0) {
      int r = expRapide(x,n/2);
      return r*r;
    } else {
      int r = expRapide(x,n/2);
      return x*r*r;
    }
  }
  public static int expRapideAcc(int x,int n,int r) {
    System.out.println("expRapideAcc("+x+","+n+","+r+")");
    if (n==0) return r;
    if (n==1) return x*r;
    if (n%2==0) {
      return expRapideAcc(x*x,n/2,r);
    } else {
      return expRapideAcc(x*x,n/2,x*r);
    }
  }
  public static int expRapideAccIter(int x,int n,int r) {
    while (true) {    
      if (n==0) return r;
      if (n==1) return x*r;
      if (n%2!=0) {
        r = x*r;
      }
      x = x*x;
      n = n/2;
    }
  }
  public static void main(String []a) {
    int N=20;
    int X = 2;
    // for (int n=10; n<N; n++) {
    //   compteur = 0;
    //   System.out.print(X+"^"+n+"="+exp(X,n));
    //   System.out.println(" Compteur="+compteur);
    // }
    // for (int n=10; n<N; n++) {
    //   compteur2 = 0;
    //   System.out.print(X+"^"+n+"="+expRapide(X,n));
    //   System.out.println(" Compteur="+compteur2);
    // }
    System.out.println(exp(2,10));
    System.out.println(expRapideAcc(2,10,1));
    System.out.println(expRapideAccIter(2,10,1));
  }
}