import java.util.Arrays;

/**
* Robert Sedgewick Algorithms in C++<br>
* Chapter 35 Random Numbers<br>
* Problem8<br>
* 加法的合同法で、例えば、b=3,c=6を用いるのが賢明でないのはなぜか?
*/
public class Chapter35RandomNumbersProblem8 {
public static void main(String[] args) {
Chapter35RandomNumbersProblem8 o = new Chapter35RandomNumbersProblem8();
o.run();
}

private void run() {
int b = 3;
int c = 6;
for (int k = 0; k < 10; k++) {
AdditiveCongruentialMethod rng = new AdditiveCongruentialMethod((int) System.nanoTime(), b, c);
rng.a[-b + rng.a.length] = 0;
rng.a[-c + rng.a.length] = 0;

int N = 1000;
int r = 100;
int[] a = new int[N];
int valid = 0;
for (int test = 0; test < 1000; test++) {
for (int i = 0; i < a.length; i++) {
a[i] = rng.nextInt(r);
}
if (simpletest(a, r)) {
valid++;
}
}
System.out.format("%10.5f\n", valid / 1000.0);
}
}

private boolean simpletest(int[] a, int r) {
return Math.abs(chisquare(a, r) - r) <= 2 * Math.sqrt(r);
}

private double chisquare(int[] a, int r) {
int N = a.length;
int[] count = new int[r];
for (int i = 0; i < N; i++) {
count[a[i]]++;
}
double t = 0;
for (int i = 0; i < count.length; i++) {
t += count[i] * count[i];
}
return t / ((double) N / r) - N;
}

private class AdditiveCongruentialMethod {
private int[] a;
private int j = 0;
private int m = 100000000;
private int m2 = 10000;
private int b;
private int c;

public AdditiveCongruentialMethod(int seed, int b, int c) {
this.b = b;
this.c = c;
a = new int[Math.max(b, c)];
seed = Math.abs(seed) % m;
a[0] = seed;
if (seed < 0 || seed >= m) {
debug("seed", seed);
throw new AssertionError();
}
for (int i = 1; i < a.length; i++) {
a[i] = (mult(a[i - 1], 31415821) + 1) % m;
if (a[i] < 0 || a[i] >= m) {
debug("a[i]", a[i], "a[i-1]", a[i - 1]);
throw new AssertionError();
}
}
}

public int nextInt(int r) {
j = (j + 1) % a.length;
a[j] = (a[(j - b + a.length) % a.length] + a[(j - c + a.length) % a.length]) % m;
int res = ((a[j] / m2) * r) / m2;
if (res < 0 || res >= r) {
throw new AssertionError();
}
return res;
}

private int mult(int a, int b) {
if (m != m2 * m2) {
throw new AssertionError();
}
int a1 = a / m2;
int a2 = a % m2;
int b1 = b / m2;
int b2 = b % m2;
if (a * b != (a1 * m2 + a2) * (b1 * m2 + b2)) {
throw new AssertionError();
}
if ((a1 * m2 + a2) * (b1 * m2 + b2) != (a1 * b1) * m + (a2 * b1 + a1 * b2) * m2 + (a2 * b2)) {
throw new AssertionError();
}
int res = (((a2 * b1 + a1 * b2) % m2) * m2 + (a2 * b2)) % m;
if (res < 0 || res >= m) {
debug("a", a, "b", b, "res", res);
throw new AssertionError();
}
return res;
}
}

private static final boolean DEBUG = true;

private static final void debug(Object... o) {
if (DEBUG)
System.err.println(Arrays.deepToString(o));
}

private static final void message(Object... o) {
System.err.println(Arrays.deepToString(o));
}

}