You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2021/08/26 17:08:37 UTC

[commons-rng] branch master updated (c3d7e60 -> da1e812)

This is an automated email from the ASF dual-hosted git repository.

aherbert pushed a change to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git.


    from c3d7e60  PMD: Allow long class for ZigguratSampler
     new 0a664f6  Update ziggurat test to target regions of the ziggurat.
     new 958245a  Disable interpolation test method
     new d8fdc7d  Update ziggurat sampler using result of the performance tests
     new da1e812  Change another mask operation to a bit shift.

The 4 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails.  The revisions
listed as "add" were already present in the repository and have only
been added to this reference.


Summary of changes:
 .../distribution/ZigguratSamplerPerformance.java   |   6 +-
 .../rng/sampling/distribution/ZigguratSampler.java | 254 +++++++++++----------
 .../sampling/distribution/StableSamplerTest.java   |  57 +++--
 .../sampling/distribution/ZigguratSamplerTest.java | 150 ++++++++++--
 4 files changed, 301 insertions(+), 166 deletions(-)

[commons-rng] 04/04: Change another mask operation to a bit shift.

Posted by ah...@apache.org.
This is an automated email from the ASF dual-hosted git repository.

aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git

commit da1e812847ad935060003536008fb4eccf569a6f
Author: aherbert <ah...@apache.org>
AuthorDate: Thu Aug 26 18:05:34 2021 +0100

    Change another mask operation to a bit shift.
---
 .../examples/jmh/sampling/distribution/ZigguratSamplerPerformance.java  | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/sampling/distribution/ZigguratSamplerPerformance.java b/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/sampling/distribution/ZigguratSamplerPerformance.java
index 1eae717..55461e6 100644
--- a/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/sampling/distribution/ZigguratSamplerPerformance.java
+++ b/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/sampling/distribution/ZigguratSamplerPerformance.java
@@ -1656,7 +1656,7 @@ public class ZigguratSamplerPerformance {
                         break;
                     }
                     // uDiff < MAX_IE (upper-right triangle) or rejected as above the curve
-                    u1 = randomInt63();
+                    u1 = nextLong() >>> 1;
                 }
             } else if (j < J_INFLECTION) {
                 if (j == 0) {

[commons-rng] 01/04: Update ziggurat test to target regions of the ziggurat.

Posted by ah...@apache.org.
This is an automated email from the ASF dual-hosted git repository.

aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git

commit 0a664f69633e317ae51cfd8a3b00af7947206a53
Author: aherbert <ah...@apache.org>
AuthorDate: Thu Aug 26 15:22:33 2021 +0100

    Update ziggurat test to target regions of the ziggurat.
    
    This targets concave, inflection, and convex overhangs and the tail of
    the Gaussian.
    
    This targets concave overhangs, and the tail of the exponential.
    
    Note: This test is still not able to identify minor errors in the sampling algorithm. The test cannot detect the difference between a concave region sampled correctly or sampled using a uniform sample from the lower-left triangle.
---
 .../sampling/distribution/ZigguratSamplerTest.java | 142 ++++++++++++++++++---
 1 file changed, 126 insertions(+), 16 deletions(-)

diff --git a/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/ZigguratSamplerTest.java b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/ZigguratSamplerTest.java
index 1955211..6633172 100644
--- a/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/ZigguratSamplerTest.java
+++ b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/ZigguratSamplerTest.java
@@ -140,6 +140,61 @@ class ZigguratSamplerTest {
         return ZigguratSampler.Exponential.of(rng).sample();
     }
 
+    // Note:
+    // The sampler samples within the box regions of the ziggurat > 98.5% of the time.
+    // The rest of the time a sample is taken from an overhang region or the tail. The proportion
+    // of samples from each of the overhangs and tail is related to the volume of those
+    // regions. The sampling within a region must fit the PDF curve of the region.
+    // We must test two items: (1) if the sampling is biased to certain overhangs;
+    // and (2) if the sampling is biased within a single overhang.
+    //
+    // The following tests check if the overall shape of the PDF is correct. Then small
+    // regions are sampled that target specific parts of the ziggurat: the overhangs and the tail.
+    // For the exponential distribution all overhangs are concave so any region can be tested.
+    // For the normal distribution the overhangs switch from convex to concave at the inflection
+    // point which is x=1. The test targets regions specifically above and below the inflection
+    // point.
+    //
+    // Testing the distribution within an overhang requires a histogram with widths smaller
+    // than the width differences in the ziggurat.
+    //
+    // For the normal distribution the widths at each end and around the inflection point are:
+    // [3.6360066255009458, 3.431550493837111, 3.3044597575834205, 3.2104230299359244]
+    // [1.0113527773194309, 1.003307168714496, 0.9951964183341382, 0.9870178156137862]
+    // [0.3881084509554052, 0.34703847379449715, 0.29172225078072095, 0.0]
+    //
+    // For the exponential:
+    // [7.569274694148063, 6.822872544335941, 6.376422694249821, 6.05490013642656]
+    // [0.18840300957360784, 0.15921172977030051, 0.12250380599214447, 0.0]
+    //
+    // Two tests are performed:
+    // (1) The bins are spaced using the quantiles of the distribution.
+    // The histogram should be uniform in frequency across all bins.
+    // (2) The bins are spaced uniformly. The frequencies should match the CDF of the function
+    // for that region. In this test the number of bins is chosen to ensure that there are multiple
+    // bins covering even the smallest gaps between ziggurat layers. Thus the bins will partition
+    // samples within a single overhang layer.
+    //
+    // Note:
+    // These tests could be improved as not all minor errors in the samplers are detected.
+    // The test does detect all the bugs that were eliminated from the algorithm during
+    // development if they are reintroduced.
+    //
+    // Bugs that cannot be detected:
+    // 1. Changing the J_INFLECTION point in the Gaussian sampler to the extremes of 1 or 253
+    //    does not fail. Thus the test cannot detect incorrect triangle sampling for
+    //    convex/concave regions. A sample that is a uniform lower-left triangle sample
+    //    for any concave region is missed by the test.
+    // 2. Changing the E_MAX threshold in the exponential sampler to 0 does not fail.
+    //    Thus the test cannot detect the difference between a uniform lower-left triangle
+    //    sample and a uniform convex region sample.
+    // This may require more samples in the histogram or a different test strategy. An example
+    // would be to force the RNG to sample outside the ziggurat boxes. The expected counts would
+    // have to be constructed using prior knowledge of the ziggurat box sizes. Thus the CDF can
+    // be computed for each overhang minus the ziggurat region underneath. No distribution
+    // exists to support this in Commons Math. A custom implementation should support computing
+    // the CDF of the ziggurat boxes from x0 to x1.
+
     /**
      * Test Gaussian samples using a large number of bins based on uniformly spaced quantiles.
      * Added for RNG-159.
@@ -152,7 +207,20 @@ class ZigguratSamplerTest {
         for (int i = 0; i < bins; i++) {
             quantiles[i] = dist.inverseCumulativeProbability((i + 1.0) / bins);
         }
-        testSamples(quantiles, false);
+        testSamples(quantiles, false,
+            // Test positive and negative ranges to check symmetry.
+            // Smallest layer is 0.292 (convex region)
+            new double[] {0, 0.2},
+            new double[] {-0.35, -0.1},
+            // Around the mean
+            new double[] {-0.1, 0.1},
+            new double[] {-0.4, 0.6},
+            // Inflection point at x=1
+            new double[] {-1.1, -0.9},
+            // A concave region
+            new double[] {2.1, 2.5},
+            // Tail = 3.64
+            new double[] {2.5, 8});
     }
 
     /**
@@ -165,12 +233,28 @@ class ZigguratSamplerTest {
         final double[] values = new double[bins];
         final double minx = -8;
         final double maxx = 8;
+        // Bin width = 16 / 2000 = 0.008
         for (int i = 0; i < bins; i++) {
             values[i] = minx + (maxx - minx) * (i + 1.0) / bins;
         }
         // Ensure upper bound is the support limit
         values[bins - 1] = Double.POSITIVE_INFINITY;
-        testSamples(values, false);
+        testSamples(values, false,
+            // Test positive and negative ranges to check symmetry.
+            // Smallest layer is 0.292 (convex region)
+            new double[] {0, 0.2},
+            new double[] {-0.35, -0.1},
+            // Around the mean
+            new double[] {-0.1, 0.1},
+            new double[] {-0.4, 0.6},
+            // Inflection point at x=1
+            new double[] {-1.01, -0.99},
+            new double[] {0.98, 1.03},
+            // A concave region
+            new double[] {1.03, 1.05},
+            // Tail = 3.64
+            new double[] {3.6, 3.8},
+            new double[] {3.7, 8});
     }
 
     /**
@@ -184,7 +268,14 @@ class ZigguratSamplerTest {
         for (int i = 0; i < bins; i++) {
             quantiles[i] = dist.inverseCumulativeProbability((i + 1.0) / bins);
         }
-        testSamples(quantiles, true);
+        testSamples(quantiles, true,
+            // Smallest layer is 0.122
+            new double[] {0, 0.1},
+            new double[] {0.05, 0.15},
+            // Around the mean
+            new double[] {0.9, 1.1},
+            // Tail = 7.57
+            new double[] {1.5, 12});
     }
 
     /**
@@ -197,24 +288,36 @@ class ZigguratSamplerTest {
         final double minx = 0;
         // Enter the tail of the distribution
         final double maxx = 12;
+        // Bin width = 12 / 2000 = 0.006
         for (int i = 0; i < bins; i++) {
             values[i] = minx + (maxx - minx) * (i + 1.0) / bins;
         }
         // Ensure upper bound is the support limit
         values[bins - 1] = Double.POSITIVE_INFINITY;
-        testSamples(values, true);
+
+        testSamples(values, true,
+            // Smallest layer is 0.122
+            new double[] {0, 0.1},
+            new double[] {0.05, 0.15},
+            // Around the mean
+            new double[] {0.9, 1.1},
+            // Tail = 7.57
+            new double[] {7.5, 7.7},
+            new double[] {7.7, 12});
     }
 
     /**
      * Test samples using the provided bins. Values correspond to the bin upper limit. It
      * is assumed the values span most of the distribution. Additional tests are performed
-     * using a region of the distribution sampled using the edge of the ziggurat.
+     * using a region of the distribution sampled.
      *
      * @param values Bin upper limits
      * @param exponential Set the true to use an exponential sampler
+     * @param ranges Ranges of the distribution to test
      */
     private static void testSamples(double[] values,
-                                    boolean exponential) {
+                                    boolean exponential,
+                                    double[]... ranges) {
         final int bins = values.length;
 
         final int samples = 10000000;
@@ -245,21 +348,28 @@ class ZigguratSamplerTest {
 
         final ChiSquareTest chiSquareTest = new ChiSquareTest();
         // Pass if we cannot reject null hypothesis that the distributions are the same.
-        final double chi2 = chiSquareTest.chiSquareTest(expected, observed);
-        Assertions.assertFalse(chi2 < 0.001,
+        final double pValue = chiSquareTest.chiSquareTest(expected, observed);
+        Assertions.assertFalse(pValue < 0.001,
             () -> String.format("(%s <= x < %s) Chi-square p-value = %s",
-                                lowerBound, values[bins - 1], chi2));
+                                lowerBound, values[bins - 1], pValue));
 
-        // Test bins sampled from the edge of the ziggurat. This is always around zero.
-        for (final double range : new double[] {0.5, 0.25, 0.1, 0.05}) {
-            final int min = findIndex(values, -range);
-            final int max = findIndex(values, range);
+        // Test regions of the ziggurat.
+        for (final double[] range : ranges) {
+            final int min = findIndex(values, range[0]);
+            final int max = findIndex(values, range[1]);
+            // Must have a range of 2
+            if (max - min + 1 < 2) {
+                // This will probably occur if the quantiles test uses too small a range
+                // for the tail. The tail is so far into the CDF that a single bin is
+                // often used to represent it.
+                Assertions.fail("Invalid range: " + Arrays.toString(range));
+            }
             final long[] observed2 = Arrays.copyOfRange(observed, min, max + 1);
             final double[] expected2 = Arrays.copyOfRange(expected, min, max + 1);
-            final double chi2b = chiSquareTest.chiSquareTest(expected2, observed2);
-            Assertions.assertFalse(chi2b < significanceLevel,
+            final double pValueB = chiSquareTest.chiSquareTest(expected2, observed2);
+            Assertions.assertFalse(pValueB < significanceLevel,
                 () -> String.format("(%s <= x < %s) Chi-square p-value = %s",
-                                    min == 0 ? lowerBound : values[min - 1], values[max], chi2b));
+                                    min == 0 ? lowerBound : values[min - 1], values[max], pValueB));
         }
     }
 

[commons-rng] 03/04: Update ziggurat sampler using result of the performance tests

Posted by ah...@apache.org.
This is an automated email from the ASF dual-hosted git repository.

aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git

commit d8fdc7d8a8c3701643181fc7b65dc6e17931f9eb
Author: aherbert <ah...@apache.org>
AuthorDate: Thu Aug 26 18:05:04 2021 +0100

    Update ziggurat sampler using result of the performance tests
    
    Use a single method to interpolate x and y. This avoids a subtraction in
    the interpolation of y.
    
    Avoid recursion in the exponential sampler.
    
    Use shifts to generate unsigned longs. This favours the upper bits of
    the uniform deviate.
    
    Each change is either mute or may have a marginal benefit depending on
    the platform. Together the sampler should be consistently performant
    across JDKs and platforms.
    
    Update tests that manipulate the output from the exponential sampler:
    stable sampler test
    ziggurat sampler test
---
 .../rng/sampling/distribution/ZigguratSampler.java | 254 +++++++++++----------
 .../sampling/distribution/StableSamplerTest.java   |  57 +++--
 .../sampling/distribution/ZigguratSamplerTest.java |   8 +-
 3 files changed, 172 insertions(+), 147 deletions(-)

diff --git a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ZigguratSampler.java b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ZigguratSampler.java
index 564b274..bac0b38 100644
--- a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ZigguratSampler.java
+++ b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ZigguratSampler.java
@@ -76,15 +76,16 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
     //
     // https://github.com/cd-mcfarland/fast_prng
     //
-    // The adaption was faithful to the original as of July-2021.
+    // The adaption was based on the reference as of July-2021.
     // The code uses similar naming conventions from the exponential.h and normal.h
     // reference. Naming has been updated to be consistent in the exponential and normal
     // samplers. Comments from the c source have been included.
-    // When the c reference was updated to use an underlying RNG
-    // available in Commons RNG outputting the same signed and positive long values
-    // the c and java code output the same random
-    // deviates over 2^30 cycles if identically seeded. Branch frequencies have
-    // been measured and added as comments.
+    // Branch frequencies have been measured and added as comments.
+    //
+    // Notable changes based on performance tests across JDKs and platforms:
+    // The generation of unsigned longs has been changed to use bit shifts to favour
+    // the significant bits of the long. The interpolation of X and Y uses a single method.
+    // Recursion in the exponential sampler has been avoided.
     //
     // Note: The c implementation uses a RNG where the current value can be obtained
     // without advancing the generator. The entry point to the sample generation
@@ -210,6 +211,7 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
     // The expressions can be evaluated from the opposite direction using (1-u), e.g:
     // y = Y[j-1] + (1-u2) * (Y[j] - Y[j-1])
     // This allows the large value to subtract the small value before multiplying by u.
+    // This method is used in the reference c code. It uses an addition subtraction to create 1-u.
     // Note that the tables X and Y have been scaled by 2^-63. This allows U to be a uniform
     // long in [0, 2^63). Thus the value c in 'c + m * x' must be scaled up by 2^63.
     //
@@ -237,8 +239,10 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
     //
     // Regions that are concave can detect a point (x,y) above the hypotenuse and reflect the
     // point in the hypotenuse by swapping u1 and u2.
+    //
     // Regions that are convex can detect a point (x,y) below the hypotenuse and immediate accept
     // the sample.
+    //
     // The maximum distance of pdf(x) from the hypotenuse can be precomputed. This can be done for
     // each region or by taking the largest distance across all regions. This value can be
     // compared to the distance between u1 and u2 and the point immediately accepted (concave)
@@ -246,7 +250,6 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
     // This sampler uses a single value for the maximum distance of pdf(x) from the hypotenuse.
     // For the normal distribution this is two values to separate the maximum for convex and
     // concave regions.
-    //
     // =========================================================================
 
     /**
@@ -517,7 +520,7 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
 
             @Override
             public double sample() {
-                return createSample() * mean;
+                return super.sample() * mean;
             }
 
             @Override
@@ -542,21 +545,9 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
         /** {@inheritDoc} */
         @Override
         public double sample() {
-            return createSample();
-        }
+            // Ideally this method byte code size should be below -XX:MaxInlineSize
+            // (which defaults to 35 bytes). This compiles to 35 bytes.
 
-        /**
-         * Creates the exponential sample with {@code mean = 1}.
-         *
-         * <p>Note: This has been extracted to a separate method so that the recursive call
-         * when sampling tries again targets this function. Otherwise the sub-class
-         * {@code ExponentialMean.sample()} method will recursively call
-         * the overloaded sample() method when trying again which creates a bad sample due
-         * to compound multiplication of the mean.
-         *
-         * @return the sample
-         */
-        final double createSample() {
             final long x = nextLong();
             // Float multiplication squashes these last 8 bits, so they can be used to sample i
             final int i = ((int) x) & MASK_INT8;
@@ -565,17 +556,60 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
                 // Early exit.
                 // Expected frequency = 0.984375
                 // Drop the sign bit to multiply by [0, 2^63).
-                return X[i] * (x & MAX_INT64);
+                return X[i] * (x >>> 1);
             }
             // Expected frequency = 0.015625
 
             // Tail frequency     = 0.000516062 (recursion)
             // Overhang frequency = 0.0151089
 
-            final int j = selectRegion();
+            // Recycle x as the upper 56 bits have not been used.
+            return edgeSample(x);
+        }
+
+        /**
+         * Create the sample from the edge of the ziggurat.
+         *
+         * <p>This method has been extracted to fit the main sample method within 35 bytes (the
+         * default size for a JVM to inline a method).
+         *
+         * @param xx Initial random deviate
+         * @return a sample
+         */
+        private double edgeSample(long xx) {
+            int j = selectRegion();
+            if (j != 0) {
+                // Expected overhang frequency = 0.966972
+                return sampleOverhang(j, xx);
+            }
+            // Expected tail frequency = 0.033028 (recursion)
+
+            // xx must be discarded as the lower bits have already been used to generate i
+
             // If the tail then exploit the memoryless property of the exponential distribution.
-            // Add a new sample to the start of the tail (X_0).
-            return j == 0 ? X_0 + createSample() : sampleOverhang(j);
+            // Perform a new sample and add it to the start of the tail.
+            // This loop sums tail values until a sample can be returned from the exponential.
+            // The sum is added to the final sample on return.
+            double x0 = X_0;
+            for (;;) {
+                // Duplicate of the sample() method
+                final long x = nextLong();
+                final int i = ((int) x) & 0xff;
+
+                if (i < I_MAX) {
+                    // Early exit.
+                    return x0 + X[i] * (x >>> 1);
+                }
+
+                // Edge of the ziggurat
+                j = selectRegion();
+                if (j != 0) {
+                    return x0 + sampleOverhang(j, x);
+                }
+
+                // Add another tail sample
+                x0 += X_0;
+            }
         }
 
         /**
@@ -595,45 +629,52 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
          * Sample from overhang region {@code j}.
          *
          * @param j Index j (must be {@code > 0})
+         * @param xx Initial random deviate
          * @return the sample
          */
-        private double sampleOverhang(int j) {
-            // Sample from the triangle:
-            //    X[j],Y[j]
-            //        |\-->u1
-            //        | \  |
-            //        |  \ |
-            //        |   \|    Overhang j (with hypotenuse not pdf(x))
-            //        |    \
-            //        |    |\
-            //        |    | \
-            //        |    u2 \
-            //        +-------- X[j-1],Y[j-1]
-            // u2 = u1 + (u2 - u1) = u1 + uDistance
-            // If u2 < u1 then reflect in the hypotenuse by swapping u1 and u2.
-            long u1 = randomInt63();
-            long uDistance = randomInt63() - u1;
-            if (uDistance < 0) {
-                // Upper-right triangle. Reflect in hypotenuse.
-                uDistance = -uDistance;
-                // Update u1 to be min(u1, u2) by subtracting the distance between them
-                u1 -= uDistance;
-            }
-            // _FAST_PRNG_SAMPLE_X(xj, ux)
-            final double x = sampleX(X, j, u1);
-            if (uDistance >= E_MAX) {
-                // Early Exit: x < y - epsilon
-                return x;
-            }
+        private double sampleOverhang(int j, long xx) {
+            // Recycle the initial random deviate.
+            // Shift right to make an unsigned long.
+            long u1 = xx >>> 1;
+            for (;;) {
+                // Sample from the triangle:
+                //    X[j],Y[j]
+                //        |\-->u1
+                //        | \  |
+                //        |  \ |
+                //        |   \|    Overhang j (with hypotenuse not pdf(x))
+                //        |    \
+                //        |    |\
+                //        |    | \
+                //        |    u2 \
+                //        +-------- X[j-1],Y[j-1]
+                // u2 = u1 + (u2 - u1) = u1 + uDistance
+                // If u2 < u1 then reflect in the hypotenuse by swapping u1 and u2.
+                long uDistance = randomInt63() - u1;
+                if (uDistance < 0) {
+                    // Upper-right triangle. Reflect in hypotenuse.
+                    uDistance = -uDistance;
+                    // Update u1 to be min(u1, u2) by subtracting the distance between them
+                    u1 -= uDistance;
+                }
+                final double x = interpolate(X, j, u1);
+                if (uDistance >= E_MAX) {
+                    // Early Exit: x < y - epsilon
+                    return x;
+                }
+
+                // Note: Frequencies have been empirically measured per call into expOverhang:
+                // Early Exit = 0.823328
+                // Accept Y   = 0.161930
+                // Reject Y   = 0.0147417 (recursion)
 
-            // Note: Frequencies have been empirically measured per call into expOverhang:
-            // Early Exit = 0.823328
-            // Accept Y   = 0.161930
-            // Reject Y   = 0.0147417 (recursion)
+                if (interpolate(Y, j, u1 + uDistance) <= Math.exp(-x)) {
+                    return x;
+                }
 
-            // _FAST_PRNG_SAMPLE_Y(j, pow(2, 63) - (ux + uDistance))
-            return sampleY(Y, j, u1 + uDistance) <= Math.exp(-x) ?
-                x : sampleOverhang(j);
+                // Generate another variate for the next iteration
+                u1 = randomInt63();
+            }
         }
 
         /** {@inheritDoc} */
@@ -988,13 +1029,11 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
         private double edgeSample(long xx) {
             // Expected frequency = 0.0117188
 
-            // Recycle bits then advance RNG:
-            // u1 = RANDOM_INT63()
+            // Drop the sign bit to create u:
             long u1 = xx & MAX_INT64;
-            // Another squashed, recyclable bit
-            // double sign_bit = u1 & 0x100 ? 1. : -1.
+            // Extract the sign bit for use later
             // Use 2 - 1 or 0 - 1
-            final double signBit = ((u1 >>> 7) & 0x2) - 1.0;
+            final double signBit = ((xx >>> 62) & 0x2) - 1.0;
             final int j = selectRegion();
             // Four kinds of overhangs:
             //  j = 0                :  Sample from tail
@@ -1009,7 +1048,7 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
                 // Expected frequency: 0.00892899
                 // Observed loop repeat frequency: 0.389804
                 for (;;) {
-                    x = sampleX(X, j, u1);
+                    x = interpolate(X, j, u1);
                     // u2 = u1 + (u2 - u1) = u1 + uDistance
                     final long uDistance = randomInt63() - u1;
                     if (uDistance >= 0) {
@@ -1020,7 +1059,7 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
                         // Within maximum distance of f(x) from the triangle hypotenuse.
                         // Frequency (per upper-right triangle): 0.431497
                         // Reject frequency: 0.489630
-                        sampleY(Y, j, u1 + uDistance) < Math.exp(-0.5 * x * x)) {
+                        interpolate(Y, j, u1 + uDistance) < Math.exp(-0.5 * x * x)) {
                         break;
                     }
                     // uDistance < MAX_IE (upper-right triangle) or rejected as above the curve
@@ -1050,9 +1089,9 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
                             // Update u1 to be min(u1, u2) by subtracting the distance between them
                             u1 -= uDistance;
                         }
-                        x = sampleX(X, j, u1);
+                        x = interpolate(X, j, u1);
                         if (uDistance > CONCAVE_E_MAX ||
-                            sampleY(Y, j, u1 + uDistance) < Math.exp(-0.5 * x * x)) {
+                            interpolate(Y, j, u1 + uDistance) < Math.exp(-0.5 * x * x)) {
                             break;
                         }
                         u1 = randomInt63();
@@ -1063,8 +1102,8 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
                 // Expected frequency: 0.000015914
                 // Observed loop repeat frequency: 0.500213
                 for (;;) {
-                    x = sampleX(X, j, u1);
-                    if (sampleY(Y, j, randomInt63()) < Math.exp(-0.5 * x * x)) {
+                    x = interpolate(X, j, u1);
+                    if (interpolate(Y, j, randomInt63()) < Math.exp(-0.5 * x * x)) {
                         break;
                     }
                     u1 = randomInt63();
@@ -1140,71 +1179,50 @@ public abstract class ZigguratSampler implements SharedStateContinuousSampler {
      * @return the long
      */
     long randomInt63() {
-        return rng.nextLong() & MAX_INT64;
+        return rng.nextLong() >>> 1;
     }
 
     /**
-     * Compute the x value of the point in the overhang region from the uniform deviate.
-     * <pre>{@code
-     *    X[j],Y[j]
-     *        |\
-     *        | \
-     *        |  \
-     *        |   \    Overhang j (with hypotenuse not pdf(x))
-     *        |    \
-     *        |     \
-     *        |      \
-     *        |-->u1  \
-     *        +-------- X[j-1],Y[j-1]
+     * Compute the value of a point using linear interpolation of a data table of values
+     * using the provided uniform deviate.
+     * <pre>
+     *  value = v[j] + u * (v[j-1] - v[j])
+     * </pre>
      *
-     *   x = X[j] + u1 * (X[j-1] - X[j])
-     * }</pre>
-     * <p>See Fig. 2 in the main text.
+     * <p>This can be used to generate the (x,y) coordinates of a point in a rectangle
+     * with the upper-left corner at {@code j} and lower-right corner at {@code j-1}:
      *
-     * @param x Precomputed ziggurat lengths, X_j = length of ziggurat layer j.
-     * @param j j
-     * @param u1 u1
-     * @return x
-     */
-    static double sampleX(double[] x, int j, long u1) {
-        return x[j] * TWO_POW_63 + u1 * (x[j - 1] - x[j]);
-    }
-
-    /**
-     * Compute the y value of the point in the overhang region from the uniform deviate.
      * <pre>{@code
      *    X[j],Y[j]
      *        |\ |
      *        | \|
      *        |  \
-     *        |  |\    Overhang j (with hypotenuse not pdf(x))
+     *        |  |\    Ziggurat overhang j (with hypotenuse not pdf(x))
      *        |  | \
      *        |  u2 \
      *        |      \
-     *        |       \
+     *        |-->u1  \
      *        +-------- X[j-1],Y[j-1]
      *
-     *   y = Y[j-1] + (1-u2) * (Y[j] - Y[j-1])
+     *   x = X[j] + u1 * (X[j-1] - X[j])
+     *   y = Y[j] + u2 * (Y[j-1] - Y[j])
      * }</pre>
-     * <p>See Fig. 2 in the main text.
      *
-     * @param y Overhang table. Y_j = f(X_j).
-     * @param j j
-     * @param u2 u2
-     * @return y
+     * @param v Ziggurat data table. Values assumed to be scaled by 2^-63.
+     * @param j Index j. Value assumed to be above zero.
+     * @param u Uniform deviate. Value assumed to be in {@code [0, 2^63)}.
+     * @return value
      */
-    static double sampleY(double[] y, int j, long u2) {
-        // Note: u2 is in [0, 2^63)
-        // Long.MIN_VALUE is used as an unsigned int with value 2^63:
-        // 1 - u2 = Long.MIN_VALUE - u2
-        //
-        // The subtraction from 1 can be avoided with:
-        // y = Y[j] + u2 * (Y[j-1] - Y[j])
-        // This is effectively sampleX(y, j, u2)
+    static double interpolate(double[] v, int j, long u) {
+        // Note:
+        // The reference code used two methods to interpolate X and Y separately.
+        // The c language exploited declared pointers to X and Y and used a #define construct.
+        // This computed X identically to this method but Y as:
+        // y = Y[j-1] + (1-u2) * (Y[j] - Y[j-1])
+        // Using a single method here clarifies the code. It avoids generating (1-u).
         // Tests show the alternative is 1 ULP different with approximately 3% frequency.
-        // It is never more than 1 ULP different.
-
-        return y[j - 1] * TWO_POW_63 + (Long.MIN_VALUE - u2) * (y[j] - y[j - 1]);
+        // It has not been measured more than 1 ULP different.
+        return v[j] * TWO_POW_63 + u * (v[j - 1] - v[j]);
     }
 
     /**
diff --git a/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/StableSamplerTest.java b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/StableSamplerTest.java
index fffe119..4f4f06d 100644
--- a/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/StableSamplerTest.java
+++ b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/StableSamplerTest.java
@@ -60,7 +60,7 @@ class StableSamplerTest {
      * This is the gap between the 2^53 dyadic rationals in [0, 1). */
     private static final double DU = 0x1.0p-53;
     /** The smallest non-zero sample from the ZigguratSampler.Exponential sampler. */
-    private static final double SMALL_W = 7.397373235160728E-19;
+    private static final double SMALL_W = 6.564735882096453E-19;
     /** A tail sample from the ZigguratSampler.Exponential after 1 recursions of the sample method.  */
     private static final double TAIL_W = 7.569274694148063;
     /** A largest sample from the ZigguratSampler.Exponential after 4 recursions of the sample method.  */
@@ -1346,7 +1346,7 @@ class StableSamplerTest {
         // The value with all bits set generates phi/2 -> pi/4.
         // Add a long to create a big value for w of 5.
         // The parameters create cancellation in the numerator of z to create a negative z.
-        final long[] longs = {Long.MAX_VALUE, 6092639261715210240L};
+        final long[] longs = {Long.MAX_VALUE, -6261465550279131136L};
 
         final double phiby2 = PI_4 - PI_4 * DU;
         final double w = 5.0;
@@ -1457,7 +1457,7 @@ class StableSamplerTest {
         final long xuHi = Long.MAX_VALUE - (1023 << 10);
         // Call sampler with smallest possible w that is not 0. This creates a finite z
         // but an infinite d due to the use of alpha -> 0.
-        final long x = 1L;
+        final long x = 3L;
         final long[] longs = {xuLo, x, xuHi, x, 0, x};
 
         assertUWSequence(new double[] {
@@ -1507,7 +1507,7 @@ class StableSamplerTest {
 
         // Add a long to create an ordinary value for w of 1.0.
         // u -> -pi/4
-        final long[] longs1 = {Long.MIN_VALUE + (1 << 10), 1446480648965178882L};
+        final long[] longs1 = {Long.MIN_VALUE + (1 << 10), 2703662416942444033L};
         assertUWSequence(new double[] {
             -PI_4 + PI_4 * DU, 1.0,
         }, longs1);
@@ -1516,7 +1516,7 @@ class StableSamplerTest {
         Assertions.assertTrue(Double.isFinite(x1), "Sampler did not recover");
 
         // u -> pi/4
-        final long[] longs2 = {Long.MAX_VALUE, 1446480648965178882L};
+        final long[] longs2 = {Long.MAX_VALUE, 2703662416942444033L};
         assertUWSequence(new double[] {
             PI_4 - PI_4 * DU, 1.0,
         }, longs2);
@@ -1619,11 +1619,11 @@ class StableSamplerTest {
 
             // Add non extreme exponential deviate to test only extreme u
             // phi/2 -> -pi/4, w=1
-            Long.MIN_VALUE + (1 << 10), 1446480648965178882L,
+            Long.MIN_VALUE + (1 << 10), 2703662416942444033L,
             // phi/2 -> pi/4, w=1
-            Long.MAX_VALUE, 1446480648965178882L,
+            Long.MAX_VALUE, 2703662416942444033L,
             // phi/2=0, w=1
-            0, 1446480648965178882L,
+            0, 2703662416942444033L,
 
             // Add non extreme uniform deviate to test only extreme w
             // phi/2=pi/5, w=0
@@ -1736,15 +1736,19 @@ class StableSamplerTest {
 
         // Extremes of the exponential sampler
         Assertions.assertEquals(0, ZigguratSampler.Exponential.of(
-                createRngWithSequence(0L)).sample(), 0.0);
+                createRngWithSequence(0L)).sample());
         Assertions.assertEquals(SMALL_W, ZigguratSampler.Exponential.of(
-                createRngWithSequence(1)).sample(), 0.0);
+                createRngWithSequence(3)).sample());
+        Assertions.assertEquals(0.5, ZigguratSampler.Exponential.of(
+                createRngWithSequence(1446480648965178882L)).sample());
         Assertions.assertEquals(1.0, ZigguratSampler.Exponential.of(
-                createRngWithSequence(1446480648965178882L)).sample(), 0.0);
+            createRngWithSequence(2703662416942444033L)).sample());
+        Assertions.assertEquals(2.5, ZigguratSampler.Exponential.of(
+                createRngWithSequence(6092639261715210240L)).sample());
         Assertions.assertEquals(5.0, ZigguratSampler.Exponential.of(
-                createRngWithSequence(6092639261715210240L)).sample(), 0.0);
+            createRngWithSequence(-6261465550279131136L)).sample());
         Assertions.assertEquals(TAIL_W, ZigguratSampler.Exponential.of(
-                createRngWithSequence(-1, -1, 0)).sample(), 0.0);
+                createRngWithSequence(-1, -1, 0)).sample());
         Assertions.assertEquals(3 * TAIL_W, ZigguratSampler.Exponential.of(
                 createRngWithSequence(-1, -1, -1, -1, -1, -1, 0)).sample(), 1e-14);
     }
@@ -1820,9 +1824,11 @@ class StableSamplerTest {
      * 1 << 10                         d
      * Long.MIN_VALUE >>> 1            pi/5
      * Long.MAX_VALUE                  pi/4 - d
-     * 1                                                   7.397373235160728E-19
-     * 1446480648965178882L                                1.0
-     * 6092639261715210240L                                5.0
+     * 3                                                   6.564735882096453E-19
+     * 1446480648965178882L                                0.5
+     * 2703662416942444033L                                1.0
+     * 6092639261715210240L                                2.5
+     * -6261465550279131136L                               5.0
      * -1, -1, 0                                           7.569274694148063
      * -1L * 2n, 0                                         n * 7.569274694148063  [2]
      * </pre>
@@ -1845,18 +1851,19 @@ class StableSamplerTest {
         // To create a certain value x the input y can be obtained by reversing the
         // computation of the corresponding precomputed factor X. The lowest 8 bits of y
         // choose the index i into X so must be set as the lowest bits.
+        // The long is shifted right 1 before multiplying by X so this must be reversed.
         //
         // To find y to obtain the sample x use:
         // double[] X = { /* from ZigguratSampler.Exponential */ }
         // double x = 1.0; // or any other value < 7.5
         // for (int i = 0; i < X.length; i++) {
-        //     // Add back the index to the lowest 8 bits.
-        //     // This will work if the number is so big that the lower bits
-        //     // are zerod when casting the 53-bit mantissa to a long.
-        //     long y = (long) (x / X[i]) + i;
-        //     if (y * X[i] == x) {
-        //         // Found y!
-        //     }
+        //      // Add back the index to the lowest 8 bits.
+        //      // This will work if the number is so big that the lower bits
+        //      // are zerod when casting the 53-bit mantissa to a long.
+        //      long y = ((long) (x / X[i]) << 1) + i;
+        //      if ((y >>> 1) * X[i] == x) {
+        //          // Found y!
+        //      }
         // }
 
         // Start with a valid RNG.
@@ -2284,7 +2291,7 @@ class StableSamplerTest {
         final double w = ZigguratSampler.Exponential.of(rng).sample();
         Assertions.assertNotEquals(0.0, w);
         // This is the actual value; it is small but not extreme.
-        Assertions.assertEquals(0.007391869818503967, w);
+        Assertions.assertEquals(0.0036959349092519837, w);
 
         final RandomSource source = RandomSource.XO_RO_SHI_RO_128_SS;
         final long seed = 0x83762b3daf1c43L;
@@ -2410,7 +2417,7 @@ class StableSamplerTest {
             // phi/2=pi/5, w=large
             x, -1, -1, -1, -1, -1, -1, -1, -1, 0,
             // phi/2=pi/5, w=1
-            x, 1446480648965178882L,
+            x, 2703662416942444033L,
         };
 
         // Validate series
diff --git a/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/ZigguratSamplerTest.java b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/ZigguratSamplerTest.java
index 6633172..6a9669a 100644
--- a/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/ZigguratSamplerTest.java
+++ b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/ZigguratSamplerTest.java
@@ -108,13 +108,13 @@ class ZigguratSamplerTest {
             // Edge value
             final double x1 = expSample(seed, -1);
             // Recursion
-            // Note the order of additions is important as the final sample is added to the
-            // tail value multiple times.
             Assertions.assertEquals(x0 + tailValue, expSample(seed, -1, -1));
             Assertions.assertEquals(x1 + tailValue, expSample(seed, -1, -1, -1));
             // Double recursion
-            Assertions.assertEquals(x0 + tailValue + tailValue, expSample(seed, -1, -1, -1, -1));
-            Assertions.assertEquals(x1 + tailValue + tailValue, expSample(seed, -1, -1, -1, -1, -1));
+            // Note the order of additions is important as the final sample is added to
+            // a summation of the tail value.
+            Assertions.assertEquals(tailValue + tailValue + x0, expSample(seed, -1, -1, -1, -1));
+            Assertions.assertEquals(tailValue + tailValue + x1, expSample(seed, -1, -1, -1, -1, -1));
         }
     }
 

[commons-rng] 02/04: Disable interpolation test method

Posted by ah...@apache.org.
This is an automated email from the ASF dual-hosted git repository.

aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git

commit 958245a7e75c5b1a6488d008bd739844097c972f
Author: aherbert <ah...@apache.org>
AuthorDate: Thu Aug 26 15:47:37 2021 +0100

    Disable interpolation test method
---
 .../jmh/sampling/distribution/ZigguratSamplerPerformance.java         | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/sampling/distribution/ZigguratSamplerPerformance.java b/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/sampling/distribution/ZigguratSamplerPerformance.java
index 58e1f41..1eae717 100644
--- a/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/sampling/distribution/ZigguratSamplerPerformance.java
+++ b/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/sampling/distribution/ZigguratSamplerPerformance.java
@@ -3922,12 +3922,12 @@ public class ZigguratSamplerPerformance {
     /**
      * Benchmark methods for obtaining an interpolated value from an unsigned long.
      *
-     * <p>Note: To be disabled. The speed is: U1, 1minusU2, U_1minusU.
+     * <p>Note: This is disabled. The speed is typically: U1, 1minusU2, U_1minusU.
      *
      * @param sources Source of randomness.
      * @return the sample value
      */
-    @Benchmark
+    //@Benchmark
     public double interpolate(InterpolationSources sources) {
         return sources.getSampler().sample();
     }