The significant refactoring to eliminate the (standard) next(int) included in these changes has the possibility of introducing subtle bugs or performance issues. Please run some tests to verify that the same sequences are generated by the 3_X code and the refactored code and benchmarks to show there is no loss in performance. It would also be good to have some additional review of this code by PRNG experts. Phil
On 12/28/15 10:23 AM, er...@apache.org wrote: > Repository: commons-math > Updated Branches: > refs/heads/master 7b62d0155 -> 81585a3c4 > > > MATH-1307 > > New base class for RNG implementations. > The source of randomness is provided through the "nextInt()" method (to be > defined in subclasses). > > > Project: http://git-wip-us.apache.org/repos/asf/commons-math/repo > Commit: http://git-wip-us.apache.org/repos/asf/commons-math/commit/4cbb388b > Tree: http://git-wip-us.apache.org/repos/asf/commons-math/tree/4cbb388b > Diff: http://git-wip-us.apache.org/repos/asf/commons-math/diff/4cbb388b > > Branch: refs/heads/master > Commit: 4cbb388ba9099be121f81d75000acc3af93bf993 > Parents: 7b62d01 > Author: Gilles <er...@apache.org> > Authored: Mon Dec 28 16:42:55 2015 +0100 > Committer: Gilles <er...@apache.org> > Committed: Mon Dec 28 16:42:55 2015 +0100 > > ---------------------------------------------------------------------- > .../math4/random/BaseRandomGenerator.java | 270 +++++++++++++++++++ > .../math4/random/BaseRandomGeneratorTest.java | 129 +++++++++ > 2 files changed, 399 insertions(+) > ---------------------------------------------------------------------- > > > http://git-wip-us.apache.org/repos/asf/commons-math/blob/4cbb388b/src/main/java/org/apache/commons/math4/random/BaseRandomGenerator.java > ---------------------------------------------------------------------- > diff --git > a/src/main/java/org/apache/commons/math4/random/BaseRandomGenerator.java > b/src/main/java/org/apache/commons/math4/random/BaseRandomGenerator.java > new file mode 100644 > index 0000000..a78fd38 > --- /dev/null > +++ b/src/main/java/org/apache/commons/math4/random/BaseRandomGenerator.java > @@ -0,0 +1,270 @@ > +/* > + * Licensed to the Apache Software Foundation (ASF) under one or more > + * contributor license agreements. See the NOTICE file distributed with > + * this work for additional information regarding copyright ownership. > + * The ASF licenses this file to You under the Apache License, Version 2.0 > + * (the "License"); you may not use this file except in compliance with > + * the License. You may obtain a copy of the License at > + * > + * http://www.apache.org/licenses/LICENSE-2.0 > + * > + * Unless required by applicable law or agreed to in writing, software > + * distributed under the License is distributed on an "AS IS" BASIS, > + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. > + * See the License for the specific language governing permissions and > + * limitations under the License. > + */ > +package org.apache.commons.math4.random; > + > +import java.io.Serializable; > + > +import org.apache.commons.math4.exception.NotStrictlyPositiveException; > +import org.apache.commons.math4.exception.OutOfRangeException; > +import org.apache.commons.math4.util.FastMath; > + > +/** > + * Abstract class implementing the methods of the {@link RandomGenerator} > + * interface in a generic way on the basis of abstract method {@link > nextInt()} > + * to be defined in subclasses. > + * > + * It also provides additional utility methods that are not part of the > + * {@link RandomGenerator} API. > + * > + * @since 4.0 > + */ > +public abstract class BaseRandomGenerator > + implements RandomGenerator, > + Serializable { > + /** Identifier for serialization. */ > + private static final long serialVersionUID = 20151227L; > + /** Next Gaussian. */ > + private double nextGaussian = Double.NaN; > + > + /** > + * {@inheritDoc} > + * > + * Basic building block for all the generic methods defined in this > class. > + * It produces the next random number according to a specific algorithm > to > + * be implemented by a subclass. > + */ > + @Override > + public abstract int nextInt(); > + > + /** {@inheritDoc} */ > + @Override > + public boolean nextBoolean() { > + return (nextInt() >>> 31) != 0; > + } > + > + /** {@inheritDoc} */ > + @Override > + public double nextDouble() { > + final long high = ((long) (nextInt() >>> 6)) << 26; > + final int low = nextInt() >>> 6; > + return (high | low) * 0x1.0p-52d; > + } > + > + /** {@inheritDoc} */ > + @Override > + public float nextFloat() { > + return (nextInt() >>> 9) * 0x1.0p-23f; > + } > + > + /** {@inheritDoc} */ > + @Override > + public double nextGaussian() { > + final double random; > + if (Double.isNaN(nextGaussian)) { > + // Generate a new pair of gaussian numbers. > + final double x = nextDouble(); > + final double y = nextDouble(); > + final double alpha = 2 * FastMath.PI * x; > + final double r = FastMath.sqrt(-2 * FastMath.log(y)); > + random = r * FastMath.cos(alpha); > + nextGaussian = r * FastMath.sin(alpha); > + } else { > + // Use the second element of the pair already generated. > + random = nextGaussian; > + nextGaussian = Double.NaN; > + } > + > + return random; > + } > + > + /** > + * {@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> > + */ > + @Override > + public int nextInt(int n) throws IllegalArgumentException { > + if (n > 0) { > + if ((n & -n) == n) { > + return (int) ((n * (long) (nextInt() >>> 1)) >> 31); > + } > + int bits; > + int val; > + do { > + bits = (nextInt() >>> 1); > + val = bits % n; > + } while (bits - val + (n - 1) < 0); > + return val; > + } > + > + throw new NotStrictlyPositiveException(n); > + } > + > + /** {@inheritDoc} */ > + @Override > + public long nextLong() { > + final long high = ((long) nextInt()) << 32; > + final long low = nextInt() & 0xffffffffL; > + return high | low; > + } > + > + /** > + * Returns a pseudorandom, uniformly distributed {@code long} value > + * between 0 (inclusive) and the specified value (exclusive), drawn from > + * this random number generator's sequence. > + * > + * @param n the bound on the random number to be returned. Must be > + * positive. > + * @return a pseudorandom, uniformly distributed {@code long} value > + * between 0 (inclusive) and n (exclusive). > + * @throws IllegalArgumentException if n is not positive. > + */ > + public long nextLong(long n) { > + if (n > 0) { > + long bits; > + long val; > + do { > + bits = ((long) (nextInt() >>> 1)) << 32; > + bits |= ((long) nextInt()) & 0xffffffffL; > + val = bits % n; > + } while (bits - val + (n - 1) < 0); > + return val; > + } > + > + throw new NotStrictlyPositiveException(n); > + } > + > + /** > + * Clears the cache used by the default implementation of > + * {@link #nextGaussian}. > + */ > + public void clear() { > + nextGaussian = Double.NaN; > + } > + > + /** > + * Generates random bytes and places them into a user-supplied array. > + * > + * <p> > + * The array is filled with bytes extracted from random integers > generated > + * using {@link #nextInt()}. > + * This implies that the number of random bytes generated may be larger > than > + * the length of the byte array. > + * </p> > + * > + * @param bytes Array in which to put the generated bytes. Cannot be > {@code null}. > + */ > + @Override > + public void nextBytes(byte[] bytes) { > + nextBytesFill(bytes, 0, bytes.length); > + } > + > + /** > + * Generates random bytes and places them into a user-supplied array. > + * > + * <p> > + * The array is filled with bytes extracted from random integers > generated > + * using {@link #nextInt()}. > + * This implies that the number of random bytes generated may be larger > than > + * the length of the byte array. > + * </p> > + * > + * @param bytes Array in which to put the generated bytes. Cannot be > {@code null}. > + * @param start Index at which to start inserting the generated bytes. > + * @param len Number of bytes to insert. > + * @throws OutOfRangeException if {@code start < 0} or {@code start >= > bytes.length}. > + * @throws OutOfRangeException if {@code len <= 0} or {@code len > > bytes.length - start}. > + */ > + public void nextBytes(byte[] bytes, > + int start, > + int len) { > + if (start < 0 || > + start >= bytes.length) { > + throw new OutOfRangeException(start, 0, bytes.length); > + } > + final int max = bytes.length - start; > + if (len <= 0 || > + len > max) { > + throw new OutOfRangeException(len, 0, max); > + } > + > + nextBytesFill(bytes, start, len); > + } > + > + /** > + * Generates random bytes and places them into a user-supplied array. > + * > + * <p> > + * The array is filled with bytes extracted from random integers > generated > + * using {@link #nextInt()}. > + * This implies that the number of random bytes generated may be larger > than > + * the length of the byte array. > + * </p> > + * > + * @param bytes Array in which to put the generated bytes. Cannot be > {@code null}. > + * @param position Index at which to start inserting the generated bytes. > + * @param length Number of bytes to insert. > + */ > + private void nextBytesFill(byte[] bytes, > + int position, > + int length) { > + int index = position; // Index of first insertion. > + > + // Index of first insertion plus multiple 4 part of length (i.e. > length > + // with two least significant bits unset). > + final int indexLoopLimit = index + (length & 0x7ffffffc); > + > + // Start filling in the byte array, 4 bytes at a time. > + while (index < indexLoopLimit) { > + final int random = nextInt(); > + bytes[index++] = (byte) random; > + bytes[index++] = (byte) (random >>> 8); > + bytes[index++] = (byte) (random >>> 16); > + bytes[index++] = (byte) (random >>> 24); > + } > + > + final int indexLimit = position + length; // Index of last insertion > + 1. > + > + // Fill in the remaining bytes. > + if (index < indexLimit) { > + int random = nextInt(); > + while (true) { > + bytes[index++] = (byte) random; > + if (index < indexLimit) { > + random >>>= 8; > + } else { > + break; > + } > + } > + } > + } > +} > > http://git-wip-us.apache.org/repos/asf/commons-math/blob/4cbb388b/src/test/java/org/apache/commons/math4/random/BaseRandomGeneratorTest.java > ---------------------------------------------------------------------- > diff --git > a/src/test/java/org/apache/commons/math4/random/BaseRandomGeneratorTest.java > b/src/test/java/org/apache/commons/math4/random/BaseRandomGeneratorTest.java > new file mode 100644 > index 0000000..40ab9b5 > --- /dev/null > +++ > b/src/test/java/org/apache/commons/math4/random/BaseRandomGeneratorTest.java > @@ -0,0 +1,129 @@ > +/* > + * Licensed to the Apache Software Foundation (ASF) under one or more > + * contributor license agreements. See the NOTICE file distributed with > + * this work for additional information regarding copyright ownership. > + * The ASF licenses this file to You under the Apache License, Version 2.0 > + * (the "License"); you may not use this file except in compliance with > + * the License. You may obtain a copy of the License at > + * > + * http://www.apache.org/licenses/LICENSE-2.0 > + * > + * Unless required by applicable law or agreed to in writing, software > + * distributed under the License is distributed on an "AS IS" BASIS, > + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. > + * See the License for the specific language governing permissions and > + * limitations under the License. > + */ > +package org.apache.commons.math4.random; > + > +import java.util.Random; > + > +import org.apache.commons.math4.exception.OutOfRangeException; > + > +import org.junit.Assert; > +import org.junit.Before; > +import org.junit.Test; > + > +/** > + * Tests for the generic implementations of the methods defined in the > + * {@link BaseRandomGenerator} class, using the standard {@link Random} > + * class as the source of randomness. > + */ > +public class BaseRandomGeneratorTest extends RandomGeneratorAbstractTest { > + /** To simplify testing of additional utility methods. */ > + protected BaseRandomGenerator baseRandomGenerator; > + > + @Before > + public void setUp() { > + baseRandomGenerator = (BaseRandomGenerator) generator; > + } > + > + @Override > + protected RandomGenerator makeGenerator() { > + final RandomGenerator generator = new TestGenerator(); > + generator.setSeed(1000); > + return generator; > + } > + > + @Test(expected=OutOfRangeException.class) > + public void testNextBytesPrecondition1() { > + final int len = 3; > + final byte[] b = new byte[len]; > + baseRandomGenerator.nextBytes(b, -1, 1); > + } > + > + @Test(expected=OutOfRangeException.class) > + public void testNextBytesPrecondition2() { > + final int len = 3; > + final byte[] b = new byte[len]; > + baseRandomGenerator.nextBytes(b, len, 0); > + } > + > + @Test(expected=OutOfRangeException.class) > + public void testNextBytesPrecondition3() { > + final int len = 3; > + final byte[] b = new byte[len]; > + baseRandomGenerator.nextBytes(b, 0, 0); > + } > + > + @Test(expected=OutOfRangeException.class) > + public void testNextBytesPrecondition4() { > + final int len = 3; > + final byte[] b = new byte[len]; > + baseRandomGenerator.nextBytes(b, 0, len + 1); > + } > + > + @Test > + public void testNextBytesSubArray() { > + final int size = 123; > + final int insert = 72; > + final int len = 37; > + > + final byte[] buffer = new byte[size]; > + baseRandomGenerator.nextBytes(buffer, insert, len); > + > + final byte[] bufferCopy = buffer.clone(); > + baseRandomGenerator.nextBytes(buffer, insert, len); > + > + for (int i = 0; i < insert; i++) { > + Assert.assertEquals(bufferCopy[i], buffer[i]); > + } > + final int maxInsert = insert + len; > + for (int i = insert; i < maxInsert; i++) { > + Assert.assertNotEquals(bufferCopy[i], buffer[i]); > + } > + for (int i = maxInsert; i < size; i++) { > + Assert.assertEquals(bufferCopy[i], buffer[i]); > + } > + } > + > + /** > + * Test RNG delegating to {@link Random}. > + */ > + private static class TestGenerator extends BaseRandomGenerator { > + /** Delegate. */ > + private Random random = new Random(); > + > + @Override > + public void setSeed(int seed) { > + random.setSeed(seed); > + clear(); > + } > + > + @Override > + public void setSeed(int[] seed) { > + random.setSeed(seed[0]); > + } > + > + @Override > + public void setSeed(long seed) { > + random.setSeed((int) seed); > + } > + > + @Override > + public int nextInt() { > + // Delegate. > + return random.nextInt(); > + } > + } > +} > > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
