import java.util.Arrays;
import java.util.Random;

/**
* Robert Sedgewick Algorithms in C++<br>
* Chapter 35 Random Numbers<br>
* Problem7<br>
* 線形合同法のパラメータを自分で決めて、1000未満の数を1000個発生させ、それらがランダムかどうかを判定する検定法を設計し適用せよ。
*/
public class Chapter35RandomNumbersProblem7 {
public static void main(String[] args) {
Chapter35RandomNumbersProblem7 o = new Chapter35RandomNumbersProblem7();
o.run();
}

private void run() {
Random rng2 = new Random();
// int b = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 +1;
// int b = (1 << 10) + -1;
int b = (int) (10000 * rng2.nextDouble());

// int m = (int) 1e8;
// int m = 1 << 24;
int m = (int) (10000 * rng2.nextDouble());
m = m * m;

debug("b", b, "m", m);

int N = 1000;
int r = 1000;
int[] a = new int[N];
for (int i = 0; i < 5; i++) {
LinearCongruentialMethod rng = new LinearCongruentialMethod((int) System.nanoTime(), b, m);
int valid = 0;
for (int j = 0; j < 1000; j++) {
for (int k = 0; k < a.length; k++) {
a[k] = 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 LinearCongruentialMethod {
private int a;
private int b;
private int m;
private int m2;

public LinearCongruentialMethod(int seed, int b, int m) {
a = Math.abs(seed) % m;
this.b = b;
this.m = m;
this.m2 = (int) Math.sqrt(m);
if (a < 0 || a >= m) {
debug("a", a, "b", b, "m", m, "seed", seed);
throw new AssertionError();
}
}

public int nextInt() {
a = (mult(a, b) + 1) % m;
if (a < 0 || a >= m) {
debug("a", a, "b", b);
throw new AssertionError();
}
return a;
}

public int nextIntBad(int r) {
a = (mult(a, b) + 1) % m;
int res = a % r;
if (res < 0 || res >= r) {
debug("a", a, "b", b, "res", res);
throw new AssertionError();
}
return res;
}

public int nextInt(int r) {
a = (mult(a, b) + 1) % m;
int res = ((a / m2) * r) / m2;
if (res < 0 || res >= r) {
debug("a", a, "b", b, "res", res);
throw new AssertionError();
}
return res;
}

private int mult(int a, int b) {
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));
}

}