commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From pste...@apache.org
Subject svn commit: r1154815 - in /commons/proper/math/trunk/src: main/java/org/apache/commons/math/random/BitsStreamGenerator.java site/xdoc/changes.xml test/java/org/apache/commons/math/random/RandomGeneratorAbstractTest.java
Date Mon, 08 Aug 2011 04:22:05 GMT
Author: psteitz
Date: Mon Aug  8 04:22:04 2011
New Revision: 1154815

URL: http://svn.apache.org/viewvc?rev=1154815&view=rev
Log:
Improved performance of nextInt(int) in BitsStreamGenerator. JIRA: MATH-642

Modified:
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/BitsStreamGenerator.java
    commons/proper/math/trunk/src/site/xdoc/changes.xml
    commons/proper/math/trunk/src/test/java/org/apache/commons/math/random/RandomGeneratorAbstractTest.java

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/BitsStreamGenerator.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/BitsStreamGenerator.java?rev=1154815&r1=1154814&r2=1154815&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/BitsStreamGenerator.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/BitsStreamGenerator.java
Mon Aug  8 04:22:04 2011
@@ -119,28 +119,35 @@ public abstract class BitsStreamGenerato
         return next(32);
     }
 
-    /** {@inheritDoc} */
+    /**
+     * {@inheritDoc}
+     * <p>This default implementation is copied from Apache Harmony
+     * java.util.Random (r929253).</p>
+     *
+     * <p>Implementation notes: <ul>
+     * <li>If n is a power of 2, this method returns
+     * {@code (int) ((n * (long) next(31)) >> 31)}.</li>
+     *
+     * <li>If n is not a power of 2, what is returned is {@code next(31) % n}
+     * with {@code next(31)} values rejected (i.e. regenerated) until a
+     * value that is larger than the remainder of {@code Integer.MAX_VALUE / n}
+     * is generated. Rejection of this initial segment is necessary to ensure
+     * a uniform distribution.</li></ul></p>
+     */
     public int nextInt(int n) throws IllegalArgumentException {
-
-        if (n < 1) {
-            throw new NotStrictlyPositiveException(n);
-        }
-
-        // find bit mask for n
-        int mask = n;
-        mask |= mask >> 1;
-        mask |= mask >> 2;
-        mask |= mask >> 4;
-        mask |= mask >> 8;
-        mask |= mask >> 16;
-
-        while (true) {
-            final int random = next(32) & mask;
-            if (random < n) {
-                return random;
+        if (n > 0) {
+            if ((n & -n) == n) {
+                return (int) ((n * (long) next(31)) >> 31);
             }
+            int bits;
+            int val;
+            do {
+                bits = next(31);
+                val = bits % n;
+            } while (bits - val + (n - 1) < 0);
+            return val;
         }
-
+        throw new NotStrictlyPositiveException(n);
     }
 
     /** {@inheritDoc} */

Modified: commons/proper/math/trunk/src/site/xdoc/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/site/xdoc/changes.xml?rev=1154815&r1=1154814&r2=1154815&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/changes.xml Mon Aug  8 04:22:04 2011
@@ -52,6 +52,9 @@ The <action> type attribute can be add,u
     If the output is not quite correct, check for invisible trailing spaces!
      -->
     <release version="3.0" date="TBD" description="TBD">
+      <action dev="psteitz" type="update" issue="MATH-642">
+        Improved performance of nextInt(int) in BitsStreamGenerator.
+      </action>
       <action dev="luc" type="fix" issue="MATH-639" >
         Fixed a wrong detection of rotation axis versus vectors plane in Rotation constructor
         using two vectors pairs.

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math/random/RandomGeneratorAbstractTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/random/RandomGeneratorAbstractTest.java?rev=1154815&r1=1154814&r2=1154815&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math/random/RandomGeneratorAbstractTest.java
(original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math/random/RandomGeneratorAbstractTest.java
Mon Aug  8 04:22:04 2011
@@ -16,6 +16,8 @@
  */
 package org.apache.commons.math.random;
 
+import java.util.Arrays;
+
 import org.apache.commons.math.TestUtils;
 import org.apache.commons.math.stat.Frequency;
 import org.apache.commons.math.stat.descriptive.SummaryStatistics;
@@ -77,30 +79,87 @@ public abstract class RandomGeneratorAbs
     public void testNextSecureHex() {}
 
     @Test
-    public void testNextIntDirect() {
+    /**
+     * Tests uniformity of nextInt(int) distribution by generating 1000
+     * samples for each of 10 test values and for each sample performing
+     * a chi-square test of homogeneity of the observed distribution with
+     * the expected uniform distribution.  Tests are performed at the .01
+     * level and an average failure rate higher than 2% (i.e. more than 20
+     * null hypothesis rejections) causes the test case to fail.
+     * 
+     * All random values are generated using the generator instance used by
+     * other tests and the generator is not reseeded, so this is a fixed seed
+     * test.
+     */
+    public void testNextIntDirect() throws Exception {
+        // Set up test values - end of the array filled randomly
+        int[] testValues = new int[] {4, 10, 12, 32, 100, 10000, 0, 0, 0, 0};
+        for (int i = 6; i < 10; i++) {
+            final int val = generator.nextInt();
+            testValues[i] = val < 0 ? -val : val + 1;
+        }
+        
+        final int numTests = 1000;
+        for (int i = 0; i < testValues.length; i++) {
+            final int n = testValues[i];
+            // Set up bins
+            int[] binUpperBounds;
+            if (n < 32) {
+                binUpperBounds = new int[n];
+                for (int k = 0; k < n; k++) {
+                    binUpperBounds[k] = k;
+                }
+            } else {
+                binUpperBounds = new int[10];
+                final int step = n / 10;
+                for (int k = 0; k < 9; k++) {
+                    binUpperBounds[k] = (k + 1) * step;
+                }
+                binUpperBounds[9] = n - 1;
+            }  
+            // Run the tests
+            int numFailures = 0;
+            final int binCount = binUpperBounds.length;
+            final long[] observed = new long[binCount];
+            final double[] expected = new double[binCount];
+            expected[0] = binUpperBounds[0] == 0 ? (double) smallSampleSize / (double) n
:
+                (double) ((binUpperBounds[0] + 1) * smallSampleSize) / (double) n;
+            for (int k = 1; k < binCount; k++) {
+                expected[k] = (double) smallSampleSize * 
+                (double) (binUpperBounds[k] - binUpperBounds[k - 1]) / (double) n;
+            }
+            for (int j = 0; j < numTests; j++) {
+                Arrays.fill(observed, 0);
+                for (int k = 0; k < smallSampleSize; k++) {
+                    final int value = generator.nextInt(n);
+                    Assert.assertTrue("nextInt range",(value >= 0) && (value <
n));
+                    for (int l = 0; l < binCount; l++) {
+                        if (binUpperBounds[l] >= value) {
+                            observed[l]++;
+                            break;
+                        }
+                    }
+                }
+                if (testStatistic.chiSquareTest(expected, observed) < 0.01) {
+                    numFailures++;
+                }  
+            }
+            if ((double) numFailures / (double) numTests > 0.02) {
+                Assert.fail("Too many failures for n = " + n +
+                " " + numFailures + " out of " + numTests + " tests failed.");
+            }
+        }
+    }
+    
+    @Test(expected=MathIllegalArgumentException.class)
+    public void testNextIntIAE() {
         try {
             generator.nextInt(-1);
             Assert.fail("MathIllegalArgumentException expected");
         } catch (MathIllegalArgumentException ex) {
             // ignored
         }
-        Frequency freq = new Frequency();
-        int value = 0;
-        for (int i=0; i<smallSampleSize; i++) {
-            value = generator.nextInt(4);
-            Assert.assertTrue("nextInt range",(value >= 0) && (value <= 3));
-            freq.addValue(value);
-        }
-        long[] observed = new long[4];
-        for (int i=0; i<4; i++) {
-            observed[i] = freq.getCount(i);
-        }
-
-        /* Use ChiSquare dist with df = 4-1 = 3, alpha = .001
-         * Change to 11.34 for alpha = .01
-         */
-        Assert.assertTrue("chi-square test -- will fail about 1 in 1000 times",
-                testStatistic.chiSquare(expected,observed) < 16.27);
+        generator.nextInt(0);
     }
 
     @Test



Mime
View raw message