package arith;

// algorithme d'Euclide

public class Euclid {

  static int gcd(int u, int v) {
  	if (v < 0) v = -v;
  	if (u < 0) u = -u;
    while (v != 0) { // invariant gcd(u,v) = gcd(u0,v0)
      int tmp = v;
      v = u % v;
      u = tmp;
    }
    return u;
  }
  
  // renvoie {a,b,g} tels quel au+bv = g = gcd(u,v)
  static int[] extendedGcdPoly(int u0, int v0) {
    int[] u = { 1, 0, u0 }, v = { 0, 1, v0 };
    while (v[2] != 0) {
      int q = u[2] / v[2];
      int[] t = { u[0] - q * v[0], u[1] - q * v[1], u[2] - q * v[2] };
      u = v;
      v = t;
    }
    return u;
  }

  static int[] extendedGcd(int u, int v) {
    int u0 = 1, u1 = 0, u2 = u, v0 = 0, v1 = 1, v2 = v;
    while (v2 != 0) {
      int q = u2 / v2;
      int t0 = u0 - q * v0, t1 = u1 - q * v1, t2 = u2 - q * v2;
      u0 = v0; u1 = v1; u2 = v2;
      v0 = t0; v1 = t1; v2 = t2;
    }
    return new int[] { u0, u1, u2 };
  }

  // division de u par v modulo m, en supposant gcd(v,m) = 1
  static int divMod(int u, int v, int m) {
  	int[] g = extendedGcd(v, m);
  	assert g[2] == 1;
  	// g[0] * v + g[1] * m = g[2] = gcd(v,m) = 1
  	int r = (g[0] * u) % m;
  	return r < 0 ? r + m : r;
  }
  
  static void check(int u, int v, int g) {
    assert (u % g == 0);
    assert (v % g == 0);
    for (int d = 1; d <= Math.min(u,  v); d++)
      if (u % d == 0 && v % d == 0)
        assert (g % d == 0);
  }
  
  public static void main(String[] args) {
    assert (gcd(0, 0) == 0);
    assert (gcd(2, 1) == 1);
    assert (gcd(2, 2) == 2);
    assert (gcd(2, 3) == 1);
    assert (gcd(2, 4) == 2);
    assert (gcd(10, 25) == 5);
    assert (gcd(-10, 25) == 5);
    assert (gcd(-10, -25) == 5);
    assert (gcd(10, -25) == 5);
    
    for (int u = 1; u <= 100; u++)
      for (int v = 1; v <= 100; v++) {
        check(u, v, gcd(u, v));
        int[] e = extendedGcd(u,  v);
        assert (e[0] * u + e[1] * v == e[2]);
        check(u, v, e[2]);
      }
    
    int m = 19;
    for (int u = 0; u < m; u++)
    	for (int v = 1; v < m; v++) {
    		int d = divMod(u, v, m);
    		assert 0 <= d && d < m;
    		assert u % m == (v * d) % m;
    	}
    
    System.out.println("Test Euclid OK");
    
//    for (int u = -10; u <= 10; u++)
//      for (int v = -10; v <= 10; v++) {
//        if (v == 0) continue;
//        System.out.println(u + " % " + v + " = " + u % v);
//      }
  }
  
}