// additive congruential generator
//   crummy little random number generator
//   this generator has not been robustly tested
// X_n = X_(n-r) + X_(n-s) mod m
//   here, we set m to be 16
//   Knuth suggests r = 24, s = 55

public class ACG extends Object {
  int state[];
  int r, s, m = 0xffff;
  private int index = 0;
  
  public ACG(int ir, int is, int seed) {
    r = ir;
    s = is;
    state = new int[is];

    int v = seed;
    for (int i = 0; i < s; i++) {
      v = 1664525 * v + 1521933251;		  // LCG values, probably wrong
      state[i] = v;
    }

    for (int i = 0; i < 5 * s; i++)		  // throw away 5s numbers
      next();
  }

  public int next() {
    int rth, sth;

    sth = state[index];
    if (r <= index)
      rth = state[index - r];
    else
      rth = state[index + s - r];
    int n = (sth + rth) & m;
    push(n);
    return n;
  }

  public void push(int n) {
    state[index] = n & m;
    index++;
    if (index >= r)
      index = 0;
  }
}