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.simple;
18  
19  import java.util.Arrays;
20  import java.util.List;
21  import java.util.ArrayList;
22  import java.util.concurrent.Callable;
23  import java.io.IOException;
24  import java.io.ObjectOutputStream;
25  import java.io.ObjectInputStream;
26  import java.io.ByteArrayOutputStream;
27  import java.io.ByteArrayInputStream;
28  
29  import org.junit.Assert;
30  import org.junit.Test;
31  import org.junit.Assume;
32  import org.junit.runner.RunWith;
33  import org.junit.runners.Parameterized;
34  import org.junit.runners.Parameterized.Parameters;
35  
36  import org.apache.commons.rng.UniformRandomProvider;
37  import org.apache.commons.rng.JumpableUniformRandomProvider;
38  import org.apache.commons.rng.LongJumpableUniformRandomProvider;
39  import org.apache.commons.rng.RandomProviderState;
40  import org.apache.commons.rng.RestorableUniformRandomProvider;
41  import org.apache.commons.rng.core.RandomProviderDefaultState;
42  import org.apache.commons.rng.core.source64.SplitMix64;
43  
44  /**
45   * Tests which all generators must pass.
46   */
47  @RunWith(value = Parameterized.class)
48  public class ProvidersCommonParametricTest {
49      /** RNG under test. */
50      private final UniformRandomProvider generator;
51      /** RNG specifier. */
52      private final RandomSource originalSource;
53      /** Seed (constructor's first parameter). */
54      private final Object originalSeed;
55      /** Constructor's additional parameters. */
56      private final Object[] originalArgs;
57  
58      /**
59       * Initializes the test instance.
60       *
61       * @param data Random source (and seed arguments) to be tested.
62       */
63      public ProvidersCommonParametricTest(ProvidersList.Data data) {
64          originalSource = data.getSource();
65          originalSeed = data.getSeed();
66          originalArgs = data.getArgs();
67          generator = RandomSource.create(originalSource, originalSeed, originalArgs);
68      }
69  
70      @Parameters(name = "{index}: data={0}")
71      public static Iterable<ProvidersList.Data[]> getList() {
72          return ProvidersList.list();
73      }
74  
75      // Seeding tests.
76  
77      @Test(expected = UnsupportedOperationException.class)
78      public void testUnsupportedSeedType() {
79          final byte seed = 123;
80          RandomSource.create(originalSource, seed, originalArgs);
81      }
82  
83      @Test
84      public void testAllSeedTypes() {
85          final Integer intSeed = -12131415;
86          final Long longSeed = -1213141516171819L;
87          final int[] intArraySeed = new int[] {0, 11, -22, 33, -44, 55, -66, 77, -88, 99};
88          final long[] longArraySeed = new long[] {11111L, -222222L, 3333333L, -44444444L};
89          final byte[] byteArraySeed = new byte[] {-128, -91, -45, -32, -1, 0, 11, 23, 54, 88, 127};
90  
91          final Object[] seeds = new Object[] {null,
92                                               intSeed,
93                                               longSeed,
94                                               intArraySeed,
95                                               longArraySeed,
96                                               byteArraySeed};
97  
98          int nonNativeSeedCount = 0;
99          int seedCount = 0;
100         for (Object s : seeds) {
101             ++seedCount;
102             if (originalSource.isNativeSeed(s)) {
103                 Assert.assertNotNull("Identified native seed is null", s);
104                 Assert.assertEquals("Incorrect identification of native seed type",
105                                     s.getClass(), originalSeed.getClass());
106             } else {
107                 ++nonNativeSeedCount;
108             }
109 
110             RandomSource.create(originalSource, s, originalArgs);
111         }
112 
113         Assert.assertEquals(6, seedCount);
114         Assert.assertEquals(5, nonNativeSeedCount);
115     }
116 
117     @Test
118     public void testNullSeed() {
119         // Note: This is the only test that explicitly calls create() with no other arguments.
120         final UniformRandomProvider rng = originalArgs == null ?
121             RandomSource.create(originalSource) :
122             RandomSource.create(originalSource, null, originalArgs);
123         checkNextIntegerInRange(rng, 10, 10000);
124     }
125 
126     @Test
127     public void testEmptyIntArraySeed() {
128         final int[] empty = new int[0];
129         Assume.assumeTrue(originalSource.isNativeSeed(empty));
130 
131         // Exercise the default seeding procedure.
132         final UniformRandomProvider rng = RandomSource.create(originalSource, empty, originalArgs);
133         checkNextIntegerInRange(rng, 10, 20000);
134     }
135 
136     @Test
137     public void testEmptyLongArraySeed() {
138         final long[] empty = new long[0];
139         Assume.assumeTrue(originalSource.isNativeSeed(empty));
140         // The Middle-Square Weyl Sequence generator cannot self-seed
141         Assume.assumeFalse(originalSource == RandomSource.MSWS);
142 
143         // Exercise the default seeding procedure.
144         final UniformRandomProvider rng = RandomSource.create(originalSource, empty, originalArgs);
145         checkNextIntegerInRange(rng, 10, 10000);
146     }
147 
148     @Test
149     public void testZeroIntArraySeed() {
150         // Exercise capacity to escape all "zero" state.
151         final int[] zero = new int[2000]; // Large enough to fill the entire state with zeroes.
152         final UniformRandomProvider rng = RandomSource.create(originalSource, zero, originalArgs);
153         Assume.assumeTrue("RNG is non-functional with an all zero seed: " + originalSource,
154                 createsNonZeroLongOutput(rng, 2000));
155         checkNextIntegerInRange(rng, 10, 10000);
156     }
157 
158     @Test
159     public void testZeroLongArraySeed() {
160         // Exercise capacity to escape all "zero" state.
161         final long[] zero = new long[2000]; // Large enough to fill the entire state with zeroes.
162         final UniformRandomProvider rng = RandomSource.create(originalSource, zero, originalArgs);
163         Assume.assumeTrue("RNG is non-functional with an all zero seed: " + originalSource,
164                 createsNonZeroLongOutput(rng, 2000));
165         checkNextIntegerInRange(rng, 10, 10000);
166     }
167 
168     @Test
169     public void testRandomSourceCreateSeed() {
170         final byte[] seed = originalSource.createSeed();
171         final UniformRandomProvider rng = RandomSource.create(originalSource, seed, originalArgs);
172         checkNextIntegerInRange(rng, 10, 10000);
173     }
174 
175     @Test
176     public void testRandomSourceCreateSeedFromRNG() {
177         final byte[] seed = originalSource.createSeed(new SplitMix64(RandomSource.createLong()));
178         final UniformRandomProvider rng = RandomSource.create(originalSource, seed, originalArgs);
179         checkNextIntegerInRange(rng, 10, 10000);
180     }
181 
182     // State save and restore tests.
183 
184     @Test
185     public void testUnrestorable() {
186         // Create two generators of the same type as the one being tested.
187         final UniformRandomProvider rng1 = RandomSource.create(originalSource, originalSeed, originalArgs);
188         final UniformRandomProvider rng2 = RandomSource.unrestorable(RandomSource.create(originalSource, originalSeed, originalArgs));
189 
190         // Ensure that they generate the same values.
191         RandomAssert.assertProduceSameSequence(rng1, rng2);
192 
193         // Cast must work.
194         final RestorableUniformRandomProvider restorable = (RestorableUniformRandomProvider) rng1;
195         // Cast must fail.
196         try {
197             final RestorableUniformRandomProvider dummy = (RestorableUniformRandomProvider) rng2;
198             Assert.fail("Cast should have failed");
199         } catch (ClassCastException e) {
200             // Expected.
201         }
202     }
203 
204     @Test
205     public void testSerializingState()
206         throws IOException,
207                ClassNotFoundException {
208         // Large "n" is not necessary here as we only test the serialization.
209         final int n = 100;
210 
211         // Cast is OK: all instances created by this library inherit from "BaseProvider".
212         final RestorableUniformRandomProvider restorable = (RestorableUniformRandomProvider) generator;
213 
214         // Save.
215         final RandomProviderState stateOrig = restorable.saveState();
216         // Serialize.
217         ByteArrayOutputStream bos = new ByteArrayOutputStream();
218         ObjectOutputStream oos = new ObjectOutputStream(bos);
219         oos.writeObject(((RandomProviderDefaultState) stateOrig).getState());
220 
221         // Store some values.
222         final List<Number> listOrig = makeList(n);
223 
224         // Discard a few more.
225         final List<Number> listDiscard = makeList(n);
226         Assert.assertTrue(listDiscard.size() != 0);
227         Assert.assertFalse(listOrig.equals(listDiscard));
228 
229         // Retrieve from serialized stream.
230         ByteArrayInputStream bis = new ByteArrayInputStream(bos.toByteArray());
231         ObjectInputStream ois = new ObjectInputStream(bis);
232         final RandomProviderState stateNew = new RandomProviderDefaultState((byte[]) ois.readObject());
233 
234         Assert.assertTrue(stateOrig != stateNew);
235 
236         // Reset.
237         restorable.restoreState(stateNew);
238 
239         // Replay.
240         final List<Number> listReplay = makeList(n);
241         Assert.assertFalse(listOrig == listReplay);
242 
243         // Check that the serialized data recreated the orginal state.
244         Assert.assertTrue(listOrig.equals(listReplay));
245     }
246 
247     @Test
248     public void testUnrestorableToString() {
249         Assert.assertEquals(generator.toString(),
250                             RandomSource.unrestorable(generator).toString());
251     }
252 
253     @Test
254     public void testSupportedInterfaces() {
255         final UniformRandomProvider rng = RandomSource.create(originalSource, null, originalArgs);
256         Assert.assertEquals("isJumpable", rng instanceof JumpableUniformRandomProvider,
257                             originalSource.isJumpable());
258         Assert.assertEquals("isLongJumpable", rng instanceof LongJumpableUniformRandomProvider,
259                             originalSource.isLongJumpable());
260     }
261 
262     ///// Support methods below.
263 
264 
265     // The methods
266     //   * makeList
267     //   * checkNextIntegerInRange
268     //   * checkNextInRange
269     // have been copied from "src/test" in module "commons-rng-core".
270     // TODO: check whether it is possible to have a single implementation.
271 
272     /**
273      * Populates a list with random numbers.
274      *
275      * @param n Loop counter.
276      * @return a list containing {@code 11 * n} random numbers.
277      */
278     private List<Number> makeList(int n) {
279         final List<Number> list = new ArrayList<Number>();
280 
281         for (int i = 0; i < n; i++) {
282             // Append 11 values.
283             list.add(generator.nextInt());
284             list.add(generator.nextInt(21));
285             list.add(generator.nextInt(436));
286             list.add(generator.nextLong());
287             list.add(generator.nextLong(157894));
288             list.add(generator.nextLong(5745833));
289             list.add(generator.nextFloat());
290             list.add(generator.nextFloat());
291             list.add(generator.nextDouble());
292             list.add(generator.nextDouble());
293             list.add(generator.nextBoolean() ? 1 : 0);
294         }
295 
296         return list;
297     }
298 
299     /**
300      * Tests uniformity of the distribution produced by {@code nextInt(int)}.
301      *
302      * @param rng Generator.
303      * @param max Upper bound.
304      * @param sampleSize Number of random values generated.
305      */
306     private void checkNextIntegerInRange(final UniformRandomProvider rng,
307                                          final int max,
308                                          int sampleSize) {
309         final Callable<Integer> nextMethod = new Callable<Integer>() {
310             @Override
311             public Integer call() throws Exception {
312                 return rng.nextInt(max);
313             }
314         };
315 
316         checkNextInRange(max, sampleSize, nextMethod);
317     }
318 
319     /**
320      * Tests uniformity of the distribution produced by the given
321      * {@code nextMethod}.
322      * It performs a chi-square test of homogeneity of the observed
323      * distribution with the expected uniform distribution.
324      * Repeat tests are performed at the 1% level and the total number of failed
325      * tests is tested at the 0.5% significance level.
326      *
327      * @param max Upper bound.
328      * @param nextMethod method to call.
329      * @param sampleSize Number of random values generated.
330      */
331     private <T extends Number> void checkNextInRange(T max,
332                                                      int sampleSize,
333                                                      Callable<T> nextMethod) {
334         final int numTests = 500;
335 
336         // Do not change (statistical test assumes that dof = 9).
337         final int numBins = 10; // dof = numBins - 1
338 
339         // Set up bins.
340         final long n = max.longValue();
341         final long[] binUpperBounds = new long[numBins];
342         final double step = n / (double) numBins;
343         for (int k = 0; k < numBins; k++) {
344             binUpperBounds[k] = (long) ((k + 1) * step);
345         }
346         // Rounding error occurs on the long value of 2305843009213693951L
347         binUpperBounds[numBins - 1] = n;
348 
349         // Run the tests.
350         int numFailures = 0;
351 
352         final double[] expected = new double[numBins];
353         long previousUpperBound = 0;
354         for (int k = 0; k < numBins; k++) {
355             final long range = binUpperBounds[k] - previousUpperBound;
356             expected[k] = sampleSize * (range / (double) n);
357             previousUpperBound = binUpperBounds[k];
358         }
359 
360         final int[] observed = new int[numBins];
361         // Chi-square critical value with 9 degrees of freedom
362         // and 1% significance level.
363         final double chi2CriticalValue = 21.67;
364 
365         try {
366             for (int i = 0; i < numTests; i++) {
367                 Arrays.fill(observed, 0);
368                 for (int j = 0; j < sampleSize; j++) {
369                     final long value = nextMethod.call().longValue();
370                     Assert.assertTrue("Range", (value >= 0) && (value < n));
371 
372                     for (int k = 0; k < numBins; k++) {
373                         if (value < binUpperBounds[k]) {
374                             ++observed[k];
375                             break;
376                         }
377                     }
378                 }
379 
380                 // Compute chi-square.
381                 double chi2 = 0;
382                 for (int k = 0; k < numBins; k++) {
383                     final double diff = observed[k] - expected[k];
384                     chi2 += diff * diff / expected[k];
385                 }
386 
387                 // Statistics check.
388                 if (chi2 > chi2CriticalValue) {
389                     ++numFailures;
390                 }
391             }
392         } catch (Exception e) {
393             // Should never happen.
394             throw new RuntimeException("Unexpected", e);
395         }
396 
397         // The expected number of failed tests can be modelled as a Binomial distribution
398         // B(n, p) with n=500, p=0.01 (500 tests with a 1% significance level).
399         // The cumulative probability of the number of failed tests (X) is:
400         // x     P(X>x)
401         // 10    0.0132
402         // 11    0.00521
403         // 12    0.00190
404 
405         if (numFailures > 11) { // Test will fail with 0.5% probability
406             Assert.fail(generator + ": Too many failures for n = " + n +
407                         " (" + numFailures + " out of " + numTests + " tests failed)");
408         }
409     }
410 
411     /**
412      * Return true if the generator creates non-zero output from
413      * {@link UniformRandomProvider#nextLong()} within the given number of cycles.
414      *
415      * @param rng Random generator.
416      * @param cycles Number of cycles.
417      * @return true if non-zero output
418      */
419     private static boolean createsNonZeroLongOutput(UniformRandomProvider rng,
420                                                     int cycles) {
421         boolean nonZero = false;
422         for (int i = 0; i < cycles; i++) {
423             if (rng.nextLong() != 0) {
424                 nonZero = true;
425             }
426         }
427         return nonZero;
428     }
429 }