package arith;

// exponentiation rapide

public class Expo {

  static int exp(int x, int n) {
    if (n == 0) return 1;
    int r = exp(x * x, n / 2);
    return n % 2 == 0 ? r : x * r;
  }
  
  // variante
  static int expAlt(int x, int n) {
    if (n == 0) return 1;
    int r = exp(x, n / 2);
    return n % 2 == 0 ? r * r : x * r * r;
  }
 
  // variante itérative
  static int expIter(int x, int n) {
  	int r = 1;
    while (n != 0) { // invariant : r * x^n = x0 ^ n0
    	if (n % 2 == 1) r *= x;
    	x *= x;
    	n /= 2;
    }
    return r;
  }

  // version générique
  static<M extends Monoid<M>> M exp(M x, int n) {
    if (n == 0) return x.unit();
    M r = exp(x.mul(x), n / 2);
    return (n % 2 == 0) ? r : x.mul(r);
  }

  public static void main(String[] args) {
  	for (int x = 0; x < 10; x++)
    	for (int n = 0; n < 10; n++) {
    		assert exp(x, n) == (int)Math.pow(x, n);
    		assert expIter(x, n) == (int)Math.pow(x, n);
   	}
    System.out.println("Test Expo OK");
  }

}