View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.rng.core;
18  
19  import java.util.Arrays;
20  import java.util.List;
21  import java.util.ArrayList;
22  import java.util.concurrent.Callable;
23  
24  import org.junit.Assert;
25  import org.junit.Test;
26  import org.junit.runner.RunWith;
27  import org.junit.runners.Parameterized;
28  import org.junit.runners.Parameterized.Parameters;
29  
30  import org.apache.commons.rng.UniformRandomProvider;
31  import org.apache.commons.rng.RestorableUniformRandomProvider;
32  import org.apache.commons.rng.RandomProviderState;
33  
34  /**
35   * Tests which all generators must pass.
36   */
37  @RunWith(value=Parameterized.class)
38  public class ProvidersCommonParametricTest {
39      /** RNG under test. */
40      private final RestorableUniformRandomProvider generator;
41  
42      /**
43       * Initializes generator instance.
44       *
45       * @param rng RNG to be tested.
46       */
47      public ProvidersCommonParametricTest(RestorableUniformRandomProvider rng) {
48          generator = rng;
49      }
50  
51      @Parameters(name = "{index}: data={0}")
52      public static Iterable<RestorableUniformRandomProvider[]> getList() {
53          return ProvidersList.list();
54      }
55  
56  
57      // Precondition tests
58  
59      @Test(expected=IllegalArgumentException.class)
60      public void testPreconditionNextInt1() {
61          generator.nextInt(-1);
62      }
63  
64      @Test(expected=IllegalArgumentException.class)
65      public void testPreconditionNextInt2() {
66          generator.nextInt(0);
67      }
68  
69      @Test(expected=IllegalArgumentException.class)
70      public void testPreconditionNextLong1() {
71          generator.nextLong(-1);
72      }
73  
74      @Test(expected=IllegalArgumentException.class)
75      public void testPreconditionNextLong2() {
76          generator.nextLong(0);
77      }
78  
79      @Test(expected=IndexOutOfBoundsException.class)
80      public void testPreconditionNextBytes1() {
81          final int size = 10;
82          final int num = 1;
83          final byte[] buf = new byte[size];
84          generator.nextBytes(buf, -1, num);
85      }
86      @Test(expected=IndexOutOfBoundsException.class)
87      public void testPreconditionNextBytes2() {
88          final int size = 10;
89          final byte[] buf = new byte[size];
90          generator.nextBytes(buf, size, 0);
91      }
92      @Test(expected=IndexOutOfBoundsException.class)
93      public void testPreconditionNextBytes3() {
94          final int size = 10;
95          final int offset = 2;
96          final byte[] buf = new byte[size];
97          generator.nextBytes(buf, offset, size - offset + 1);
98      }
99      @Test(expected=IndexOutOfBoundsException.class)
100     public void testPreconditionNextBytes4() {
101         final int size = 10;
102         final int offset = 1;
103         final byte[] buf = new byte[size];
104         generator.nextBytes(buf, offset, -1);
105     }
106 
107 
108     // Uniformity tests
109 
110     @Test
111     public void testUniformNextBytesFullBuffer() {
112         // Value chosen to exercise all the code lines in the
113         // "nextBytes" methods.
114         final int size = 23;
115         final byte[] buffer = new byte[size];
116 
117         final Runnable nextMethod = new Runnable() {
118             @Override
119             public void run() {
120                 generator.nextBytes(buffer);
121             }
122         };
123 
124         Assert.assertTrue(isUniformNextBytes(buffer, 0, size, nextMethod));
125     }
126 
127     @Test
128     public void testUniformNextBytesPartialBuffer() {
129         final int totalSize = 1234;
130         final int offset = 567;
131         final int size = 89;
132 
133         final byte[] buffer = new byte[totalSize];
134 
135         final Runnable nextMethod = new Runnable() {
136             @Override
137             public void run() {
138                 generator.nextBytes(buffer, offset, size);
139             }
140         };
141 
142         // Test should pass for the part of the buffer where values are put.
143         Assert.assertTrue(isUniformNextBytes(buffer, offset, offset + size, nextMethod));
144 
145         // Test must fail for the parts of the buffer where no values are put.
146         Assert.assertFalse(isUniformNextBytes(buffer, 0, offset, nextMethod));
147         Assert.assertFalse(isUniformNextBytes(buffer, offset + size, buffer.length, nextMethod));
148     }
149 
150     @Test
151     public void testUniformNextIntegerInRange() {
152         // Statistical test uses 10 bins so tests are invalid below this level
153         checkNextIntegerInRange(10, 1000);
154         checkNextIntegerInRange(12, 1000);
155         checkNextIntegerInRange(31, 1000);
156         checkNextIntegerInRange(32, 1000);
157         checkNextIntegerInRange(2016128993, 1000);
158         checkNextIntegerInRange(1834691456, 1000);
159         checkNextIntegerInRange(869657561, 1000);
160         checkNextIntegerInRange(1570504788, 1000);
161     }
162 
163     @Test
164     public void testUniformNextLongInRange() {
165         // Statistical test uses 10 bins so tests are invalid below this level
166         checkNextLongInRange(11, 1000);
167         checkNextLongInRange(19, 1000);
168         checkNextLongInRange(31, 1000);
169         checkNextLongInRange(32, 1000);
170 
171         final long q = Long.MAX_VALUE / 4;
172         checkNextLongInRange(q, 1000);
173         checkNextLongInRange(2 * q, 1000);
174         checkNextLongInRange(3 * q, 1000);
175     }
176 
177     @Test
178     public void testUniformNextFloat() {
179         checkNextFloat(1000);
180     }
181 
182     @Test
183     public void testUniformNextDouble() {
184         checkNextDouble(1000);
185     }
186 
187     @Test
188     public void testUniformNextIntRandomWalk() {
189         final Callable<Boolean> nextMethod = new Callable<Boolean>() {
190             @Override
191             public Boolean call() throws Exception {
192                 return generator.nextInt() >= 0;
193             }
194         };
195 
196         checkRandomWalk(1000, nextMethod);
197     }
198 
199     @Test
200     public void testUniformNextLongRandomWalk() {
201         final Callable<Boolean> nextMethod = new Callable<Boolean>() {
202             @Override
203             public Boolean call() throws Exception {
204                 return generator.nextLong() >= 0;
205             }
206         };
207 
208         checkRandomWalk(1000, nextMethod);
209     }
210 
211     @Test
212     public void testUniformNextBooleanRandomWalk() {
213         final Callable<Boolean> nextMethod = new Callable<Boolean>() {
214             @Override
215             public Boolean call() throws Exception {
216                 return generator.nextBoolean();
217             }
218         };
219 
220         checkRandomWalk(1000, nextMethod);
221     }
222 
223     // State save and restore tests.
224 
225     @Test
226     public void testStateSettable() {
227         // Should be fairly large in order to ensure that all the internal
228         // state is away from its initial settings.
229         final int n = 10000;
230 
231         // Save.
232         final RandomProviderState state = generator.saveState();
233         // Store some values.
234         final List<Number> listOrig = makeList(n);
235         // Discard a few more.
236         final List<Number> listDiscard = makeList(n);
237         Assert.assertTrue(listDiscard.size() != 0);
238         Assert.assertFalse(listOrig.equals(listDiscard));
239         // Reset.
240         generator.restoreState(state);
241         // Replay.
242         final List<Number> listReplay = makeList(n);
243         Assert.assertFalse(listOrig == listReplay);
244         // Check that the restored state is the same as the original.
245         Assert.assertTrue(listOrig.equals(listReplay));
246     }
247 
248     @Test(expected=IllegalStateException.class)
249     public void testStateWrongSize() {
250         final RandomProviderState state = new DummyGenerator().saveState();
251         // Try to restore with an invalid state (wrong size).
252         generator.restoreState(state);
253     }
254 
255     @Test(expected=IllegalArgumentException.class)
256     public void testRestoreForeignState() {
257         generator.restoreState(new RandomProviderState() {});
258     }
259 
260 
261     ///// Support methods below.
262 
263     /**
264      * Populates a list with random numbers.
265      *
266      * @param n Loop counter.
267      * @return a list containing {@code 11 * n} random numbers.
268      */
269     private List<Number> makeList(int n) {
270         final List<Number> list = new ArrayList<Number>();
271 
272         for (int i = 0; i < n; i++) {
273             // Append 11 values.
274             list.add(generator.nextInt());
275             list.add(generator.nextInt(21));
276             list.add(generator.nextInt(436));
277             list.add(generator.nextLong());
278             list.add(generator.nextLong(157894));
279             list.add(generator.nextLong(5745833));
280             list.add(generator.nextFloat());
281             list.add(generator.nextFloat());
282             list.add(generator.nextDouble());
283             list.add(generator.nextDouble());
284             list.add(generator.nextBoolean() ? 1 : 0);
285         }
286 
287         return list;
288     }
289 
290     /**
291      * Checks that the generator values can be placed into 256 bins with
292      * approximately equal number of counts.
293      * Test allows to select only part of the buffer for performing the
294      * statistics.
295      *
296      * @param buffer Buffer to be filled.
297      * @param first First element (included) of {@code buffer} range for
298      * which statistics must be taken into account.
299      * @param last Last element (excluded) of {@code buffer} range for
300      * which statistics must be taken into account.
301      * @param nextMethod Method that fills the given {@code buffer}.
302      * @return {@code true} if the distribution is uniform.
303      */
304     private boolean isUniformNextBytes(byte[] buffer,
305                                        int first,
306                                        int last,
307                                        Runnable nextMethod) {
308         final int sampleSize = 10000;
309 
310         // Number of possible values (do not change).
311         final int byteRange = 256;
312         // Chi-square critical value with 256 degrees of freedom
313         // and 1% significance level.
314         final double chi2CriticalValue = 311.560343;
315         // To transform a byte value into its bin index.
316         final int byteRangeOffset = 128;
317 
318         // Bins.
319         final long[] observed = new long[byteRange];
320         final double[] expected = new double[byteRange];
321 
322         for (int i = 0; i < byteRange; i++) {
323             expected[i] = sampleSize * (last - first) / (double) byteRange;
324         }
325 
326         try {
327             for (int k = 0; k < sampleSize; k++) {
328                 nextMethod.run();
329 
330                 for (int i = first; i < last; i++) {
331                     final byte b = buffer[i];
332                     ++observed[b + byteRangeOffset];
333                 }
334             }
335         } catch (Exception e) {
336             // Should never happen.
337             throw new RuntimeException("Unexpected");
338         }
339 
340         // Compute chi-square.
341         double chi2 = 0;
342         for (int k = 0; k < byteRange; k++) {
343             final double diff = observed[k] - expected[k];
344             chi2 += diff * diff / expected[k];
345         }
346 
347         // Statistics check.
348         return chi2 < chi2CriticalValue;
349     }
350 
351     /**
352      * Checks that the generator values can be placed into 2 bins with
353      * approximately equal number of counts.
354      * The test uses the expectation from a fixed-step "random walk".
355      *
356      * @param nextMethod Method that returns {@code true} if the generated
357      * values are to be placed in the first bin, {@code false} if it must
358      * go to the second bin.
359      */
360     private void checkRandomWalk(int sampleSize,
361                                  Callable<Boolean> nextMethod) {
362         int walk = 0;
363 
364         try {
365             for (int k = 0; k < sampleSize; ++k) {
366                 if (nextMethod.call()) {
367                     ++walk;
368                 } else {
369                     --walk;
370                 }
371             }
372         } catch (Exception e) {
373             // Should never happen.
374             throw new RuntimeException("Unexpected");
375         }
376 
377         final double actual = Math.abs(walk);
378         final double max = Math.sqrt(sampleSize) * 2.576;
379         Assert.assertTrue(generator + ": Walked too far astray: " + actual +
380                           " > " + max +
381                           " (test will fail randomly about 1 in 100 times)",
382                           actual < max);
383     }
384 
385     /**
386      * Tests uniformity of the distribution produced by {@code nextInt(int)}.
387      *
388      * @param max Upper bound.
389      * @param sampleSize Number of random values generated.
390      */
391     private void checkNextIntegerInRange(final int max,
392                                          int sampleSize) {
393         checkNextIntegerInRange(generator, max, sampleSize);
394     }
395 
396     /**
397      * Tests uniformity of the distribution produced by {@code nextInt(int)}.
398      *
399      * @param rng Generator.
400      * @param max Upper bound.
401      * @param sampleSize Number of random values generated.
402      */
403     private void checkNextIntegerInRange(final UniformRandomProvider rng,
404                                          final int max,
405                                          int sampleSize) {
406         final Callable<Integer> nextMethod = new Callable<Integer>() {
407             @Override
408             public Integer call() throws Exception {
409                 return rng.nextInt(max);
410             }
411         };
412 
413         checkNextInRange(max, sampleSize, nextMethod);
414     }
415 
416     /**
417      * Tests uniformity of the distribution produced by {@code nextLong(long)}.
418      *
419      * @param max Upper bound.
420      * @param sampleSize Number of random values generated.
421      */
422     private void checkNextLongInRange(final long max,
423                                       int sampleSize) {
424         final Callable<Long> nextMethod = new Callable<Long>() {
425             @Override
426             public Long call() throws Exception {
427                 return generator.nextLong(max);
428             }
429         };
430 
431         checkNextInRange(max, sampleSize, nextMethod);
432     }
433 
434     /**
435      * Tests uniformity of the distribution produced by {@code nextFloat()}.
436      *
437      * @param sampleSize Number of random values generated.
438      */
439     private void checkNextFloat(int sampleSize) {
440         final int max = 1234;
441         final Callable<Integer> nextMethod = new Callable<Integer>() {
442             @Override
443             public Integer call() throws Exception {
444                 return (int) (max * generator.nextFloat());
445             }
446         };
447 
448         checkNextInRange(max, sampleSize, nextMethod);
449     }
450 
451     /**
452      * Tests uniformity of the distribution produced by {@code nextDouble()}.
453      *
454      * @param sampleSize Number of random values generated.
455      */
456     private void checkNextDouble(int sampleSize) {
457         final int max = 578;
458         final Callable<Integer> nextMethod = new Callable<Integer>() {
459             @Override
460             public Integer call() throws Exception {
461                 return (int) (max * generator.nextDouble());
462             }
463         };
464 
465         checkNextInRange(max, sampleSize, nextMethod);
466     }
467 
468     /**
469      * Tests uniformity of the distribution produced by the given
470      * {@code nextMethod}.
471      * It performs a chi-square test of homogeneity of the observed
472      * distribution with the expected uniform distribution.
473      * Tests are performed at the 1% level and an average failure rate
474      * higher than 2% causes the test case to fail.
475      *
476      * @param max Upper bound.
477      * @param nextMethod method to call.
478      * @param sampleSize Number of random values generated.
479      */
480     private <T extends Number> void checkNextInRange(T max,
481                                                      int sampleSize,
482                                                      Callable<T> nextMethod) {
483         final int numTests = 500;
484 
485         // Do not change (statistical test assumes that dof = 9).
486         final int numBins = 10; // dof = numBins - 1
487 
488         // Set up bins.
489         final long n = max.longValue();
490         final long[] binUpperBounds = new long[numBins];
491         final double step = n / (double) numBins;
492         for (int k = 0; k < numBins; k++) {
493             binUpperBounds[k] = (long) ((k + 1) * step);
494         }
495         // Rounding error occurs on the long value of 2305843009213693951L
496         binUpperBounds[numBins - 1] = n;
497 
498         // Run the tests.
499         int numFailures = 0;
500 
501         final double[] expected = new double[numBins];
502         long previousUpperBound = 0;
503         for (int k = 0; k < numBins; k++) {
504             final long range = binUpperBounds[k] - previousUpperBound;
505             expected[k] = sampleSize * (range / (double) n);
506             previousUpperBound = binUpperBounds[k];
507         }
508 
509         final int[] observed = new int[numBins];
510         // Chi-square critical value with 9 degrees of freedom
511         // and 1% significance level.
512         final double chi2CriticalValue = 21.67;
513 
514         try {
515             for (int i = 0; i < numTests; i++) {
516                 Arrays.fill(observed, 0);
517                 for (int j = 0; j < sampleSize; j++) {
518                     final long value = nextMethod.call().longValue();
519                     Assert.assertTrue("Range", (value >= 0) && (value < n));
520 
521                     for (int k = 0; k < numBins; k++) {
522                         if (value < binUpperBounds[k]) {
523                             ++observed[k];
524                             break;
525                         }
526                     }
527                 }
528 
529                 // Compute chi-square.
530                 double chi2 = 0;
531                 for (int k = 0; k < numBins; k++) {
532                     final double diff = observed[k] - expected[k];
533                     chi2 += diff * diff / expected[k];
534                 }
535 
536                 // Statistics check.
537                 if (chi2 > chi2CriticalValue) {
538                     ++numFailures;
539                 }
540             }
541         } catch (Exception e) {
542             // Should never happen.
543             throw new RuntimeException("Unexpected", e);
544         }
545 
546         // The expected number of failed tests can be modelled as a Binomial distribution
547         // B(n, p) with n=500, p=0.01 (500 tests with a 1% significance level).
548         // The cumulative probability of the number of failed tests (X) is:
549         // x     P(X>x)
550         // 10    0.0132
551         // 11    0.00521
552         // 12    0.00190
553 
554         if (numFailures > 11) { // Test will fail with 0.5% probability
555             Assert.fail(generator + ": Too many failures for n = " + n +
556                         " (" + numFailures + " out of " + numTests + " tests failed)");
557         }
558     }
559 
560     /**
561      * @param rng Generator.
562      * @param chunkSize Size of the small buffer.
563      * @param numChunks Number of chunks that make the large buffer.
564      */
565     static void checkNextBytesChunks(RestorableUniformRandomProvider rng,
566                                      int chunkSize,
567                                      int numChunks) {
568         final byte[] b1 = new byte[chunkSize * numChunks];
569         final byte[] b2 = new byte[chunkSize];
570 
571         final RandomProviderState state = rng.saveState();
572 
573         // Generate the chunks in a single call.
574         rng.nextBytes(b1);
575 
576         // Reset to previous state.
577         rng.restoreState(state);
578 
579         // Generate the chunks in consecutive calls.
580         for (int i = 0; i < numChunks; i++) {
581             rng.nextBytes(b2);
582         }
583 
584         // Store last "chunkSize" bytes of b1 into b3.
585         final byte[] b3 = new byte[chunkSize];
586         System.arraycopy(b1, b1.length - b3.length, b3, 0, b3.length);
587 
588         // Sequence of calls must be the same.
589         Assert.assertArrayEquals("chunkSize=" + chunkSize + " numChunks=" + numChunks,
590                                  b2, b3);
591     }
592 
593     /**
594      * Dummy class for checking that restoring fails when an invalid state is used.
595      */
596     class DummyGenerator extends org.apache.commons.rng.core.source32.IntProvider {
597         /** {@inheritDoc} */
598         @Override
599         public int next() {
600             return 4; // https://www.xkcd.com/221/
601         }
602 
603         /** {@inheritDoc} */
604         @Override
605         protected byte[] getStateInternal() {
606             return new byte[0];
607         }
608 
609         /** {@inheritDoc} */
610         @Override
611         protected void setStateInternal(byte[] s) {
612             // No state.
613         }
614     }
615 }