You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by lu...@apache.org on 2013/03/10 20:02:54 UTC
svn commit: r1454897 - in /commons/proper/math/trunk/src: changes/
main/java/org/apache/commons/math3/random/
main/java/org/apache/commons/math3/stat/ranking/
test/java/org/apache/commons/math3/random/
test/java/org/apache/commons/math3/stat/ranking/
Author: luc
Date: Sun Mar 10 19:02:54 2013
New Revision: 1454897
URL: http://svn.apache.org/r1454897
Log:
Fixed generation of long random numbers between two bounds.
We now directly use discrete raw values to build the int/double instead
of relying on floating point arithmetic.
JIRA: MATH-936
Modified:
commons/proper/math/trunk/src/changes/changes.xml
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/random/BitsStreamGenerator.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/random/RandomDataGenerator.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/stat/ranking/NaturalRanking.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/random/MersenneTwisterTest.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/random/RandomDataGeneratorTest.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/random/Well512aTest.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/stat/ranking/NaturalRankingTest.java
Modified: commons/proper/math/trunk/src/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/changes/changes.xml?rev=1454897&r1=1454896&r2=1454897&view=diff
==============================================================================
--- commons/proper/math/trunk/src/changes/changes.xml (original)
+++ commons/proper/math/trunk/src/changes/changes.xml Sun Mar 10 19:02:54 2013
@@ -55,10 +55,13 @@ This is a minor release: It combines bug
Changes to existing features were made in a backwards-compatible
way such as to allow drop-in replacement of the v3.1[.1] JAR file.
">
+ <action dev="luc" type="fix" issue="MATH-936" >
+ Fixed generation of long random numbers between two bounds.
+ </action>
<action dev="luc" type="fix" issue="MATH-942" due-to="Piotr Wydrych" >
Fixed creation of generic array.
</action>
- <action dev="luc" type="add" issue="MATH-914" >
+ <action dev="luc" type="add" issue="MATH-914" >
Check bounds in multi-start vector optimizers.
</action>
<action dev="luc" type="add" issue="MATH-941" due-to="Piotr Wydrych" >
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/random/BitsStreamGenerator.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/random/BitsStreamGenerator.java?rev=1454897&r1=1454896&r2=1454897&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/random/BitsStreamGenerator.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/random/BitsStreamGenerator.java Sun Mar 10 19:02:54 2013
@@ -163,6 +163,31 @@ public abstract class BitsStreamGenerato
}
/**
+ * Returns a pseudorandom, uniformly distributed <tt>long</tt> 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 <tt>long</tt>
+ * value between 0 (inclusive) and n (exclusive).
+ * @throws IllegalArgumentException if n is not positive.
+ */
+ public long nextLong(long n) throws IllegalArgumentException {
+ if (n > 0) {
+ long bits;
+ long val;
+ do {
+ bits = ((long) next(31)) << 32;
+ bits = bits | (((long) next(32)) & 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}.
*/
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/random/RandomDataGenerator.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/random/RandomDataGenerator.java?rev=1454897&r1=1454896&r2=1454897&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/random/RandomDataGenerator.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/random/RandomDataGenerator.java Sun Mar 10 19:02:54 2013
@@ -45,7 +45,6 @@ import org.apache.commons.math3.exceptio
import org.apache.commons.math3.exception.NumberIsTooLargeException;
import org.apache.commons.math3.exception.OutOfRangeException;
import org.apache.commons.math3.exception.util.LocalizedFormats;
-import org.apache.commons.math3.util.FastMath;
/**
* Implements the {@link RandomData} interface using a {@link RandomGenerator}
@@ -194,25 +193,82 @@ public class RandomDataGenerator impleme
}
/** {@inheritDoc} */
- public int nextInt(int lower, int upper) throws NumberIsTooLargeException {
+ public int nextInt(final int lower, final int upper) throws NumberIsTooLargeException {
if (lower >= upper) {
throw new NumberIsTooLargeException(LocalizedFormats.LOWER_BOUND_NOT_BELOW_UPPER_BOUND,
lower, upper, false);
}
- double r = getRan().nextDouble();
- double scaled = r * upper + (1.0 - r) * lower + r;
- return (int) FastMath.floor(scaled);
+ final int max = (upper - lower) + 1;
+ if (max <= 0) {
+ // the range is too wide to fit in a positive int (larger than 2^31); as it covers
+ // more than half the integer range, we use directly a simple rejection method
+ final RandomGenerator rng = getRan();
+ while (true) {
+ final int r = rng.nextInt();
+ if (r >= lower && r <= upper) {
+ return r;
+ }
+ }
+ } else {
+ // we can shift the range and generate directly a positive int
+ return lower + getRan().nextInt(max);
+ }
}
/** {@inheritDoc} */
- public long nextLong(long lower, long upper) throws NumberIsTooLargeException {
+ public long nextLong(final long lower, final long upper) throws NumberIsTooLargeException {
if (lower >= upper) {
throw new NumberIsTooLargeException(LocalizedFormats.LOWER_BOUND_NOT_BELOW_UPPER_BOUND,
lower, upper, false);
}
- double r = getRan().nextDouble();
- double scaled = r * upper + (1.0 - r) * lower + r;
- return (long)FastMath.floor(scaled);
+ final long max = (upper - lower) + 1;
+ if (max <= 0) {
+ // the range is too wide to fit in a positive long (larger than 2^63); as it covers
+ // more than half the long range, we use directly a simple rejection method
+ final RandomGenerator rng = getRan();
+ while (true) {
+ final long r = rng.nextLong();
+ if (r >= lower && r <= upper) {
+ return r;
+ }
+ }
+ } else if (max < Integer.MAX_VALUE){
+ // we can shift the range and generate directly a positive int
+ return lower + getRan().nextInt((int) max);
+ } else {
+ // we can shift the range and generate directly a positive long
+ return lower + nextLong(getRan(), max);
+ }
+ }
+
+ /**
+ * Returns a pseudorandom, uniformly distributed <tt>long</tt> 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 <tt>long</tt>
+ * value between 0 (inclusive) and n (exclusive).
+ * @throws IllegalArgumentException if n is not positive.
+ */
+ private static long nextLong(final RandomGenerator rng, final long n) throws IllegalArgumentException {
+ if (n > 0) {
+ final byte[] byteArray = new byte[8];
+ long bits;
+ long val;
+ do {
+ rng.nextBytes(byteArray);
+ bits = 0;
+ for (final byte b : byteArray) {
+ bits = (bits << 8) | (((long) b) & 0xffL);
+ }
+ bits = bits & 0x7fffffffffffffffL;
+ val = bits % n;
+ } while (bits - val + (n - 1) < 0);
+ return val;
+ }
+ throw new NotStrictlyPositiveException(n);
}
/**
@@ -282,27 +338,82 @@ public class RandomDataGenerator impleme
}
/** {@inheritDoc} */
- public int nextSecureInt(int lower, int upper) throws NumberIsTooLargeException {
+ public int nextSecureInt(final int lower, final int upper) throws NumberIsTooLargeException {
if (lower >= upper) {
throw new NumberIsTooLargeException(LocalizedFormats.LOWER_BOUND_NOT_BELOW_UPPER_BOUND,
lower, upper, false);
}
- SecureRandom sec = getSecRan();
- final double r = sec.nextDouble();
- final double scaled = r * upper + (1.0 - r) * lower + r;
- return (int)FastMath.floor(scaled);
+ final int max = (upper - lower) + 1;
+ if (max <= 0) {
+ // the range is too wide to fit in a positive int (larger than 2^31); as it covers
+ // more than half the integer range, we use directly a simple rejection method
+ final SecureRandom rng = getSecRan();
+ while (true) {
+ final int r = rng.nextInt();
+ if (r >= lower && r <= upper) {
+ return r;
+ }
+ }
+ } else {
+ // we can shift the range and generate directly a positive int
+ return lower + getSecRan().nextInt(max);
+ }
}
/** {@inheritDoc} */
- public long nextSecureLong(long lower, long upper) throws NumberIsTooLargeException {
+ public long nextSecureLong(final long lower, final long upper) throws NumberIsTooLargeException {
if (lower >= upper) {
throw new NumberIsTooLargeException(LocalizedFormats.LOWER_BOUND_NOT_BELOW_UPPER_BOUND,
lower, upper, false);
}
- SecureRandom sec = getSecRan();
- final double r = sec.nextDouble();
- final double scaled = r * upper + (1.0 - r) * lower + r;
- return (long)FastMath.floor(scaled);
+ final long max = (upper - lower) + 1;
+ if (max <= 0) {
+ // the range is too wide to fit in a positive long (larger than 2^63); as it covers
+ // more than half the long range, we use directly a simple rejection method
+ final SecureRandom rng = getSecRan();
+ while (true) {
+ final long r = rng.nextLong();
+ if (r >= lower && r <= upper) {
+ return r;
+ }
+ }
+ } else if (max < Integer.MAX_VALUE){
+ // we can shift the range and generate directly a positive int
+ return lower + getSecRan().nextInt((int) max);
+ } else {
+ // we can shift the range and generate directly a positive long
+ return lower + nextLong(getSecRan(), max);
+ }
+ }
+
+ /**
+ * Returns a pseudorandom, uniformly distributed <tt>long</tt> 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 <tt>long</tt>
+ * value between 0 (inclusive) and n (exclusive).
+ * @throws IllegalArgumentException if n is not positive.
+ */
+ private static long nextLong(final SecureRandom rng, final long n) throws IllegalArgumentException {
+ if (n > 0) {
+ final byte[] byteArray = new byte[8];
+ long bits;
+ long val;
+ do {
+ rng.nextBytes(byteArray);
+ bits = 0;
+ for (final byte b : byteArray) {
+ bits = (bits << 8) | (((long) b) & 0xffL);
+ }
+ bits = bits & 0x7fffffffffffffffL;
+ val = bits % n;
+ } while (bits - val + (n - 1) < 0);
+ return val;
+ }
+ throw new NotStrictlyPositiveException(n);
}
/**
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/stat/ranking/NaturalRanking.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/stat/ranking/NaturalRanking.java?rev=1454897&r1=1454896&r2=1454897&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/stat/ranking/NaturalRanking.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/stat/ranking/NaturalRanking.java Sun Mar 10 19:02:54 2013
@@ -24,8 +24,7 @@ import java.util.List;
import org.apache.commons.math3.exception.MathInternalError;
import org.apache.commons.math3.exception.NotANumberException;
-import org.apache.commons.math3.random.RandomData;
-import org.apache.commons.math3.random.RandomDataImpl;
+import org.apache.commons.math3.random.RandomDataGenerator;
import org.apache.commons.math3.random.RandomGenerator;
import org.apache.commons.math3.util.FastMath;
@@ -84,7 +83,7 @@ public class NaturalRanking implements R
private final TiesStrategy tiesStrategy;
/** Source of random data - used only when ties strategy is RANDOM */
- private final RandomData randomData;
+ private final RandomDataGenerator randomData;
/**
* Create a NaturalRanking with default strategies for handling ties and NaNs.
@@ -105,7 +104,7 @@ public class NaturalRanking implements R
super();
this.tiesStrategy = tiesStrategy;
nanStrategy = DEFAULT_NAN_STRATEGY;
- randomData = new RandomDataImpl();
+ randomData = new RandomDataGenerator();
}
/**
@@ -130,7 +129,7 @@ public class NaturalRanking implements R
super();
this.nanStrategy = nanStrategy;
this.tiesStrategy = tiesStrategy;
- randomData = new RandomDataImpl();
+ randomData = new RandomDataGenerator();
}
/**
@@ -143,7 +142,7 @@ public class NaturalRanking implements R
super();
this.tiesStrategy = TiesStrategy.RANDOM;
nanStrategy = DEFAULT_NAN_STRATEGY;
- randomData = new RandomDataImpl(randomGenerator);
+ randomData = new RandomDataGenerator(randomGenerator);
}
@@ -159,7 +158,7 @@ public class NaturalRanking implements R
super();
this.nanStrategy = nanStrategy;
this.tiesStrategy = TiesStrategy.RANDOM;
- randomData = new RandomDataImpl(randomGenerator);
+ randomData = new RandomDataGenerator(randomGenerator);
}
/**
Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/random/MersenneTwisterTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/random/MersenneTwisterTest.java?rev=1454897&r1=1454896&r2=1454897&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/random/MersenneTwisterTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/random/MersenneTwisterTest.java Sun Mar 10 19:02:54 2013
@@ -23,7 +23,7 @@ public class MersenneTwisterTest extends
@Override
protected RandomGenerator makeGenerator() {
- return new MersenneTwister(100);
+ return new MersenneTwister(111);
}
// TODO: Some of the tests moved up to RandomGeneratorAbstractTest tested alternative seeding / constructors
Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/random/RandomDataGeneratorTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/random/RandomDataGeneratorTest.java?rev=1454897&r1=1454896&r2=1454897&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/random/RandomDataGeneratorTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/random/RandomDataGeneratorTest.java Sun Mar 10 19:02:54 2013
@@ -113,25 +113,26 @@ public class RandomDataGeneratorTest {
checkNextIntUniform(-3, 6);
}
}
-
+
@Test
public void testNextIntNegativeRange() {
for (int i = 0; i < 5; i++) {
checkNextIntUniform(-7, -4);
checkNextIntUniform(-15, -2);
+ checkNextIntUniform(Integer.MIN_VALUE + 1, Integer.MIN_VALUE + 12);
}
}
-
+
@Test
public void testNextIntPositiveRange() {
for (int i = 0; i < 5; i++) {
checkNextIntUniform(0, 3);
checkNextIntUniform(2, 12);
checkNextIntUniform(1,2);
+ checkNextIntUniform(Integer.MAX_VALUE - 12, Integer.MAX_VALUE - 1);
}
}
-
-
+
private void checkNextIntUniform(int min, int max) {
final Frequency freq = new Frequency();
for (int i = 0; i < smallSampleSize; i++) {
@@ -153,6 +154,24 @@ public class RandomDataGeneratorTest {
}
@Test
+ public void testNextIntWideRange() {
+ int lower = -0x6543210F;
+ int upper = 0x456789AB;
+ int max = Integer.MIN_VALUE;
+ int min = Integer.MAX_VALUE;
+ for (int i = 0; i < 1000000; ++i) {
+ int r = randomData.nextInt(lower, upper);
+ max = FastMath.max(max, r);
+ min = FastMath.min(min, r);
+ Assert.assertTrue(r >= lower);
+ Assert.assertTrue(r <= upper);
+ }
+ double ratio = (((double) max) - ((double) min)) /
+ (((double) upper) - ((double) lower));
+ Assert.assertTrue(ratio > 0.99999);
+ }
+
+ @Test
public void testNextLongIAE() {
try {
randomData.nextLong(4, 3);
@@ -161,7 +180,7 @@ public class RandomDataGeneratorTest {
// ignored
}
}
-
+
@Test
public void testNextLongNegativeToPositiveRange() {
for (int i = 0; i < 5; i++) {
@@ -169,31 +188,34 @@ public class RandomDataGeneratorTest {
checkNextLongUniform(-3, 6);
}
}
-
+
@Test
public void testNextLongNegativeRange() {
for (int i = 0; i < 5; i++) {
checkNextLongUniform(-7, -4);
checkNextLongUniform(-15, -2);
+ checkNextLongUniform(Long.MIN_VALUE + 1, Long.MIN_VALUE + 12);
}
}
-
+
@Test
public void testNextLongPositiveRange() {
for (int i = 0; i < 5; i++) {
checkNextLongUniform(0, 3);
checkNextLongUniform(2, 12);
+ checkNextLongUniform(Long.MAX_VALUE - 12, Long.MAX_VALUE - 1);
}
}
-
- private void checkNextLongUniform(int min, int max) {
+
+ private void checkNextLongUniform(long min, long max) {
final Frequency freq = new Frequency();
for (int i = 0; i < smallSampleSize; i++) {
final long value = randomData.nextLong(min, max);
- Assert.assertTrue("nextLong range", (value >= min) && (value <= max));
+ Assert.assertTrue("nextLong range: " + value + " " + min + " " + max,
+ (value >= min) && (value <= max));
freq.addValue(value);
}
- final int len = max - min + 1;
+ final int len = ((int) (max - min)) + 1;
final long[] observed = new long[len];
for (int i = 0; i < len; i++) {
observed[i] = freq.getCount(min + i);
@@ -207,6 +229,24 @@ public class RandomDataGeneratorTest {
}
@Test
+ public void testNextLongWideRange() {
+ long lower = -0x6543210FEDCBA987L;
+ long upper = 0x456789ABCDEF0123L;
+ long max = Long.MIN_VALUE;
+ long min = Long.MAX_VALUE;
+ for (int i = 0; i < 10000000; ++i) {
+ long r = randomData.nextLong(lower, upper);
+ max = FastMath.max(max, r);
+ min = FastMath.min(min, r);
+ Assert.assertTrue(r >= lower);
+ Assert.assertTrue(r <= upper);
+ }
+ double ratio = (((double) max) - ((double) min)) /
+ (((double) upper) - ((double) lower));
+ Assert.assertTrue(ratio > 0.99999);
+ }
+
+ @Test
public void testNextSecureLongIAE() {
try {
randomData.nextSecureLong(4, 3);
Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/random/Well512aTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/random/Well512aTest.java?rev=1454897&r1=1454896&r2=1454897&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/random/Well512aTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/random/Well512aTest.java Sun Mar 10 19:02:54 2013
@@ -23,7 +23,7 @@ public class Well512aTest extends Random
@Override
public RandomGenerator makeGenerator() {
- return new Well512a(100);
+ return new Well512a(101);
}
@Test
public void testReferenceCode() {
Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/stat/ranking/NaturalRankingTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/stat/ranking/NaturalRankingTest.java?rev=1454897&r1=1454896&r2=1454897&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/stat/ranking/NaturalRankingTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/stat/ranking/NaturalRankingTest.java Sun Mar 10 19:02:54 2013
@@ -176,22 +176,22 @@ public class NaturalRankingTest {
NaturalRanking ranking = new NaturalRanking(NaNStrategy.FIXED,
randomGenerator);
double[] ranks = ranking.rank(exampleData);
- double[] correctRanks = { 5, 4, 6, 7, 3, 8, Double.NaN, 1, 4 };
+ double[] correctRanks = { 5, 3, 6, 7, 3, 8, Double.NaN, 1, 2 };
TestUtils.assertEquals(correctRanks, ranks, 0d);
ranks = ranking.rank(tiesFirst);
- correctRanks = new double[] { 1, 1, 4, 3, 5 };
+ correctRanks = new double[] { 1, 2, 4, 3, 5 };
TestUtils.assertEquals(correctRanks, ranks, 0d);
ranks = ranking.rank(tiesLast);
- correctRanks = new double[] { 3, 4, 2, 1 };
+ correctRanks = new double[] { 3, 3, 2, 1 };
TestUtils.assertEquals(correctRanks, ranks, 0d);
ranks = ranking.rank(multipleNaNs);
correctRanks = new double[] { 1, 2, Double.NaN, Double.NaN };
TestUtils.assertEquals(correctRanks, ranks, 0d);
ranks = ranking.rank(multipleTies);
- correctRanks = new double[] { 3, 2, 5, 5, 7, 6, 1 };
+ correctRanks = new double[] { 3, 2, 4, 4, 6, 7, 1 };
TestUtils.assertEquals(correctRanks, ranks, 0d);
ranks = ranking.rank(allSame);
- correctRanks = new double[] { 1, 3, 4, 4 };
+ correctRanks = new double[] { 2, 3, 3, 3 };
TestUtils.assertEquals(correctRanks, ranks, 0d);
}