1 /* 2 * Copyright (c) 2012, 2021, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 package test.java.util.Random; 24 25 import java.util.ArrayList; 26 import java.util.List; 27 import java.util.PrimitiveIterator; 28 29 import java.util.random.*; 30 31 import java.util.Set; 32 import java.util.concurrent.CompletableFuture; 33 import java.util.concurrent.ExecutionException; 34 import java.util.concurrent.ThreadLocalRandom; 35 import java.util.concurrent.TimeUnit; 36 import java.util.concurrent.TimeoutException; 37 import java.util.function.IntSupplier; 38 import java.util.function.LongSupplier; 39 import java.util.function.BooleanSupplier; 40 import java.util.function.Supplier; 41 import java.util.function.Function; 42 import java.util.stream.Stream; 43 44 import static java.util.stream.Collectors.toList; 45 import static java.util.stream.Collectors.toSet; 46 47 /** 48 * @test 49 * @summary test bit sequences produced by clases that implement interface RandomGenerator 50 * @bug 8248862 51 * @run main RandomTestChiSquared 52 * @key randomness 53 */ 54 55 public class RandomTestChiSquared { 56 57 static String currentRNG = ""; 58 static int failCount = 0; 59 exceptionOnFail()60 static void exceptionOnFail() { 61 if (failCount != 0) { 62 throw new RuntimeException(failCount + " fails detected"); 63 } 64 } 65 setRNG(String rng)66 static void setRNG(String rng) { 67 currentRNG = rng; 68 } 69 fail(String format, Object... args)70 static void fail(String format, Object... args) { 71 if (currentRNG.length() != 0) { 72 System.err.println(currentRNG); 73 currentRNG = ""; 74 } 75 76 System.err.format(" " + format, args); 77 failCount++; 78 } 79 80 // Some simple chi-squared tests similar to that used for the FIPS 140 poker test, 81 // but intended primarily to test production of random values from ranges. 82 83 private static final int SEQUENCE_SIZE = 20000; 84 85 // Entry k of this table was computed in Microsoft Excel using the formulae 86 // =CHISQ.INV(0.0000000777517,k) and =CHISQ.INV.RT(0.00000142611,k) 87 // (except that entry 0 is a dummy and should never be used). 88 static final double[][] chiSquaredBounds = { 89 { 0.0, 0.0 }, 90 { 9.49598E-15, 23.24513154 }, 91 { 1.55503E-07, 26.92112020 }, 92 { 4.40485E-05, 29.93222467 }, 93 { 0.000788782, 32.62391510 }, 94 { 0.004636947, 35.11665045 }, 95 { 0.015541535, 37.46947634 }, 96 { 0.037678318, 39.71667636 }, 97 { 0.074471919, 41.88031518 }, 98 { 0.128297057, 43.97561646 }, 99 { 0.200566433, 46.01362542 }, 100 { 0.291944952, 48.00266676 }, 101 { 0.402564694, 49.94920504 }, 102 { 0.532199236, 51.85838271 }, 103 { 0.680392565, 53.73437242 }, 104 { 0.846549931, 55.58061674 }, 105 { 1.030000010, 57.39999630 }, 106 { 1.230036580, 59.19495111 }, 107 { 1.445945898, 60.96756998 }, 108 { 1.677024296, 62.71965780 }, 109 { 1.922589129, 64.45278706 }, 110 { 2.181985238, 66.16833789 }, 111 { 2.454588423, 67.86752964 }, 112 { 2.739806923, 69.55144602 }, 113 { 3.037081611, 71.22105544 }, 114 { 3.345885349, 72.87722754 }, 115 { 3.665721841, 74.52074682 }, 116 { 3.996124178, 76.15232388 }, 117 { 4.336653242, 77.77260487 }, 118 { 4.686896041, 79.38217943 }, 119 { 5.046464051, 80.98158736 }, 120 { 5.414991603, 82.57132439 } 121 }; 122 123 124 125 // N is the number of categories; every element of s ought to be in [0,N). 126 // N must be in [1,31]. chiSquaredTest(String id, int N, IntSupplier theSupplier)127 static boolean chiSquaredTest(String id, int N, IntSupplier theSupplier) { 128 int[] stats = new int[N]; 129 for (int j = 0; j < SEQUENCE_SIZE; j++) { 130 int v = theSupplier.getAsInt(); 131 // assert((0 <= v) && (v < N)); 132 ++stats[v]; 133 } 134 int z = 0; 135 for (int k = 0; k < stats.length; k++) { 136 z += stats[k]*stats[k]; 137 } 138 double x = ((double)N / (double)SEQUENCE_SIZE) * (double)z - (double)SEQUENCE_SIZE; 139 double lo = chiSquaredBounds[N][0]; 140 double hi = chiSquaredBounds[N][1]; 141 boolean chiSquaredSuccess = ((lo < x) && (x < hi)); 142 if (!chiSquaredSuccess) fail("chi-squared test failure for %s: x=%g (should be in [%g,%g])\n", id, x, lo, hi); 143 return chiSquaredSuccess; 144 } 145 testRngChiSquared(String id, int N, IntSupplier theSupplier)146 static boolean testRngChiSquared(String id, int N, IntSupplier theSupplier) { 147 if (chiSquaredTest(id, N, theSupplier)) return true; 148 fail("testRngChiSquared glitch"); 149 return chiSquaredTest(id, N, theSupplier) && chiSquaredTest(id, N, theSupplier); 150 } 151 tryIt(RandomGenerator rng, String kind, Function<String,BooleanSupplier> f)152 static void tryIt(RandomGenerator rng, String kind, Function<String,BooleanSupplier> f) { 153 String id = rng.getClass().getName() + " " + kind; 154 // System.out.printf("Testing %s\n", id); 155 boolean success = f.apply(id).getAsBoolean(); 156 if (!success) { 157 fail("*** Failure of %s\n", id); 158 } 159 } 160 161 // To test one instance of an RandomGenerator with the BSI test suite, we test: 162 // nextInt() 163 // nextLong() 164 // nextBoolean() 165 // ints() 166 // longs() 167 // doubles() 168 // nextDouble() 169 // nextFloat() 170 171 static final int[] testSizes = { 11, 13, 16, 17, 19, 23, 24 }; 172 testOneRng(RandomGenerator rng, int failureTolerance)173 static void testOneRng(RandomGenerator rng, int failureTolerance) { 174 String name = rng.getClass().getName(); 175 for (int j = 0; j < testSizes.length; j++) { 176 int N = testSizes[j]; 177 tryIt(rng, "nextInt(" + N + ")", (String id) -> () -> testRngChiSquared(id, N, () -> rng.nextInt(N))); 178 tryIt(rng, "nextInt(43, " + (N+43) + ")", (String id) -> () -> testRngChiSquared(id, N, () -> rng.nextInt(43, N+43) - 43)); 179 tryIt(rng, "nextInt(-59, " + (N-59) + ")", (String id) -> () -> testRngChiSquared(id, N, () -> rng.nextInt(-59, N-59) + 59)); 180 } 181 for (int j = 0; j < testSizes.length; j++) { 182 int N = testSizes[j]; 183 tryIt(rng, "nextLong(" + N + ")", (String id) -> () -> testRngChiSquared(id, N, () -> (int)(rng.nextLong(N)))); 184 tryIt(rng, "nextLong(43, " + (N+43) + ")", (String id) -> () -> testRngChiSquared(id, N, () -> (int)(rng.nextLong(43, N+43) - 43))); 185 tryIt(rng, "nextLong(-59, " + (N-59) + ")", (String id) -> () -> testRngChiSquared(id, N, () -> (int)(rng.nextLong(-59, N-59) + 59))); 186 } 187 for (int j = 0; j < testSizes.length; j++) { 188 int N = testSizes[j]; 189 tryIt(rng, "nextFloat(" + N + ")", (String id) -> () -> testRngChiSquared(id, N, () -> (int)(rng.nextFloat(N)) % N)); 190 tryIt(rng, "nextFloat(43, " + (N+43) + ")", (String id) -> () -> testRngChiSquared(id, N, () -> (int)(rng.nextFloat(43, N+43) - 43) % N)); 191 tryIt(rng, "nextFloat(-59, " + (N-59) + ")", (String id) -> () -> testRngChiSquared(id, N, () -> (int)(rng.nextFloat(-59, N-59) + 59) % N)); 192 } 193 for (int j = 0; j < testSizes.length; j++) { 194 int N = testSizes[j]; 195 tryIt(rng, "nextDouble(" + N + ")", (String id) -> () -> testRngChiSquared(id, N, () -> (int)(rng.nextDouble(N)) % N)); 196 tryIt(rng, "nextDouble(43, " + (N+43) + ")", (String id) -> () -> testRngChiSquared(id, N, () -> (int)(rng.nextDouble(43, N+43) - 43) % N)); 197 tryIt(rng, "nextDouble(-59, " + (N-59) + ")", (String id) -> () -> testRngChiSquared(id, N, () -> (int)(rng.nextDouble(-59, N-59) + 59) % N)); 198 } 199 for (int j = 0; j < testSizes.length; j++) { 200 int N = testSizes[j]; 201 PrimitiveIterator.OfInt iter1 = rng.ints(0, N).iterator(); 202 tryIt(rng, "ints(0, " + N + ")", (String id) -> () -> testRngChiSquared(id, N, iter1::next)); 203 PrimitiveIterator.OfInt iter2 = rng.ints(43, N+43).iterator(); 204 tryIt(rng, "ints(43, " + (N+43) + ")", (String id) -> () -> testRngChiSquared(id, N, () -> iter2.next() - 43)); 205 PrimitiveIterator.OfInt iter3 = rng.ints(-59, N-59).iterator(); 206 tryIt(rng, "ints(-59, " + (N-59) + ")", (String id) -> () -> testRngChiSquared(id, N, () -> iter3.next() + 59)); 207 } 208 for (int j = 0; j < testSizes.length; j++) { 209 int N = testSizes[j]; 210 PrimitiveIterator.OfLong iter1 = rng.longs(0, N).iterator(); 211 tryIt(rng, "longs(0, " + N + ")", (String id) -> () -> testRngChiSquared(id, N, () -> (int)(iter1.next() + 0))); 212 PrimitiveIterator.OfLong iter2 = rng.longs(43, N+43).iterator(); 213 tryIt(rng, "longs(43, " + (N+43) + ")", (String id) -> () -> testRngChiSquared(id, N, () -> (int)(iter2.next() - 43))); 214 PrimitiveIterator.OfLong iter3 = rng.longs(-59, N-59).iterator(); 215 tryIt(rng, "longs(-59, " + (N-59) + ")", (String id) -> () -> testRngChiSquared(id, N, () -> (int)(iter3.next() + 59))); 216 } 217 for (int j = 0; j < testSizes.length; j++) { 218 int N = testSizes[j]; 219 PrimitiveIterator.OfDouble iter1 = rng.doubles(0, N).iterator(); 220 tryIt(rng, "doubles(0, " + N + ")", (String id) -> () -> testRngChiSquared(id, N, () -> (int)(iter1.next() + 0) % N)); 221 PrimitiveIterator.OfDouble iter2 = rng.doubles(43, N+43).iterator(); 222 tryIt(rng, "doubles(43, " + (N+43) + ")", (String id) -> () -> testRngChiSquared(id, N, () -> (int)(iter2.next() - 43) % N)); 223 PrimitiveIterator.OfDouble iter3 = rng.doubles(-59, N-59).iterator(); 224 tryIt(rng, "doubles(-59, " + (N-59) + ")", (String id) -> () -> testRngChiSquared(id, N, () -> (int)(iter3.next() + 59) % N)); 225 } 226 } 227 main(String[] args)228 public static void main(String[] args) { 229 RandomGeneratorFactory.all() 230 .filter(f -> !f.name().equals("SecureRandom")) 231 .forEach(factory -> { 232 setRNG(factory.name()); 233 234 if (factory.name().equals("Random")) { 235 testOneRng(factory.create(417), 1); 236 } else { 237 testOneRng(factory.create(417), 0); 238 } 239 }); 240 241 exceptionOnFail(); 242 } 243 244 } 245 246