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 2010/09/21 21:50:44 UTC
svn commit: r999577 - in /commons/proper/math/trunk/src:
main/java/org/apache/commons/math/random/ site/xdoc/ site/xdoc/userguide/
Author: luc
Date: Tue Sep 21 19:50:43 2010
New Revision: 999577
URL: http://svn.apache.org/viewvc?rev=999577&view=rev
Log:
improved documentation (javadoc, code comments about optimization and userguide)
JIRA: MATH-419
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/AbstractWell.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well1024a.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well19937a.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well19937c.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well44497a.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well44497b.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well512a.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/package.html
commons/proper/math/trunk/src/site/xdoc/changes.xml
commons/proper/math/trunk/src/site/xdoc/userguide/random.xml
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/AbstractWell.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/AbstractWell.java?rev=999577&r1=999576&r2=999577&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/AbstractWell.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/AbstractWell.java Tue Sep 21 19:50:43 2010
@@ -26,7 +26,8 @@ import java.io.Serializable;
* Pierre L'Ecuyer and Makoto Matsumoto <a
* href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf">Improved
* Long-Period Generators Based on Linear Recurrences Modulo 2</a> ACM
- * Transactions on Mathematical Software, 32, 1 (2006).</p>
+ * Transactions on Mathematical Software, 32, 1 (2006). The errata for the paper
+ * are in <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt">wellrng-errata.txt</a>.</p>
* @see <a href="http://www.iro.umontreal.ca/~panneton/WELLRNG.html">WELL Random number generator</a>
* @version $Revision$ $Date$
@@ -36,23 +37,27 @@ import java.io.Serializable;
public abstract class AbstractWell extends BitsStreamGenerator implements Serializable {
/** Serializable version identifier. */
- private static final long serialVersionUID = -8068371019303673353L;
-
- /** Bit mask preserving the first w - p bits in a w bits block. */
- protected final int mp;
-
- /** Bit mask preserving the last p bits in a w bits block. */
- protected final int mpTilde;
+ private static final long serialVersionUID = -817701723016583596L;
/** Current index in the bytes pool. */
protected int index;
/** Bytes pool. */
protected final int[] v;
+
+ /** Index indirection table giving for each index its predecessor taking table size into account. */
protected final int[] iRm1;
+
+ /** Index indirection table giving for each index its second predecessor taking table size into account. */
protected final int[] iRm2;
+
+ /** Index indirection table giving for each index the value index + m1 taking table size into account. */
protected final int[] i1;
+
+ /** Index indirection table giving for each index the value index + m2 taking table size into account. */
protected final int[] i2;
+
+ /** Index indirection table giving for each index the value index + m3 taking table size into account. */
protected final int[] i3;
/** Creates a new random number generator.
@@ -93,15 +98,11 @@ public abstract class AbstractWell exten
// and p is the number of unused bits in the last block
final int w = 32;
final int r = (k + w - 1) / w;
- final int p = r * w - k;
-
- // set up generator parameters
- this.mp = (-1) << p;
- this.mpTilde = ~mp;
- this.v = new int[r];
- this.index = 0;
+ this.v = new int[r];
+ this.index = 0;
- // set up indirection indices
+ // precompute indirection index tables. These tables are used for optimizing access
+ // they allow saving computations like "(j + r - 2) % r" with costly modulo operations
iRm1 = new int[r];
iRm2 = new int[r];
i1 = new int[r];
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well1024a.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well1024a.java?rev=999577&r1=999576&r2=999577&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well1024a.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well1024a.java Tue Sep 21 19:50:43 2010
@@ -24,7 +24,8 @@ package org.apache.commons.math.random;
* Pierre L'Ecuyer and Makoto Matsumoto <a
* href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf">Improved
* Long-Period Generators Based on Linear Recurrences Modulo 2</a> ACM
- * Transactions on Mathematical Software, 32, 1 (2006).</p>
+ * Transactions on Mathematical Software, 32, 1 (2006). The errata for the paper
+ * are in <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt">wellrng-errata.txt</a>.</p>
* @see <a href="http://www.iro.umontreal.ca/~panneton/WELLRNG.html">WELL Random number generator</a>
* @version $Revision$ $Date$
@@ -82,7 +83,6 @@ public class Well1024a extends AbstractW
protected int next(final int bits) {
final int indexRm1 = iRm1[index];
- final int indexRm2 = iRm2[index];
final int v0 = v[index];
final int vM1 = v[i1[index]];
@@ -97,7 +97,6 @@ public class Well1024a extends AbstractW
v[index] = z3;
v[indexRm1] = z4;
- v[indexRm2] &= mp;
index = indexRm1;
return z4 >>> (32 - bits);
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well19937a.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well19937a.java?rev=999577&r1=999576&r2=999577&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well19937a.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well19937a.java Tue Sep 21 19:50:43 2010
@@ -24,7 +24,8 @@ package org.apache.commons.math.random;
* Pierre L'Ecuyer and Makoto Matsumoto <a
* href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf">Improved
* Long-Period Generators Based on Linear Recurrences Modulo 2</a> ACM
- * Transactions on Mathematical Software, 32, 1 (2006).</p>
+ * Transactions on Mathematical Software, 32, 1 (2006). The errata for the paper
+ * are in <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt">wellrng-errata.txt</a>.</p>
* @see <a href="http://www.iro.umontreal.ca/~panneton/WELLRNG.html">WELL Random number generator</a>
* @version $Revision$ $Date$
@@ -97,7 +98,7 @@ public class Well19937a extends Abstract
v[index] = z3;
v[indexRm1] = z4;
- v[indexRm2] &= mp;
+ v[indexRm2] &= 0x80000000;
index = indexRm1;
return z4 >>> (32 - bits);
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well19937c.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well19937c.java?rev=999577&r1=999576&r2=999577&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well19937c.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well19937c.java Tue Sep 21 19:50:43 2010
@@ -24,7 +24,8 @@ package org.apache.commons.math.random;
* Pierre L'Ecuyer and Makoto Matsumoto <a
* href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf">Improved
* Long-Period Generators Based on Linear Recurrences Modulo 2</a> ACM
- * Transactions on Mathematical Software, 32, 1 (2006).</p>
+ * Transactions on Mathematical Software, 32, 1 (2006). The errata for the paper
+ * are in <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt">wellrng-errata.txt</a>.</p>
* @see <a href="http://www.iro.umontreal.ca/~panneton/WELLRNG.html">WELL Random number generator</a>
* @version $Revision$ $Date$
@@ -97,7 +98,7 @@ public class Well19937c extends Abstract
v[index] = z3;
v[indexRm1] = z4;
- v[indexRm2] &= mp;
+ v[indexRm2] &= 0x80000000;
index = indexRm1;
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well44497a.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well44497a.java?rev=999577&r1=999576&r2=999577&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well44497a.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well44497a.java Tue Sep 21 19:50:43 2010
@@ -24,7 +24,8 @@ package org.apache.commons.math.random;
* Pierre L'Ecuyer and Makoto Matsumoto <a
* href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf">Improved
* Long-Period Generators Based on Linear Recurrences Modulo 2</a> ACM
- * Transactions on Mathematical Software, 32, 1 (2006).</p>
+ * Transactions on Mathematical Software, 32, 1 (2006). The errata for the paper
+ * are in <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt">wellrng-errata.txt</a>.</p>
* @see <a href="http://www.iro.umontreal.ca/~panneton/WELLRNG.html">WELL Random number generator</a>
* @version $Revision$ $Date$
@@ -89,6 +90,7 @@ public class Well44497a extends Abstract
final int vM2 = v[i2[index]];
final int vM3 = v[i3[index]];
+ // the values below include the errata of the original article
final int z0 = (0xFFFF8000 & v[indexRm1]) ^ (0x00007FFF & v[indexRm2]);
final int z1 = (v0 ^ (v0 << 24)) ^ (vM1 ^ (vM1 >>> 30));
final int z2 = (vM2 ^ (vM2 << 10)) ^ (vM3 << 26);
@@ -99,7 +101,7 @@ public class Well44497a extends Abstract
v[index] = z3;
v[indexRm1] = z4;
- v[indexRm2] &= mp;
+ v[indexRm2] &= 0xFFFF8000;
index = indexRm1;
return z4 >>> (32 - bits);
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well44497b.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well44497b.java?rev=999577&r1=999576&r2=999577&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well44497b.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well44497b.java Tue Sep 21 19:50:43 2010
@@ -24,7 +24,8 @@ package org.apache.commons.math.random;
* Pierre L'Ecuyer and Makoto Matsumoto <a
* href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf">Improved
* Long-Period Generators Based on Linear Recurrences Modulo 2</a> ACM
- * Transactions on Mathematical Software, 32, 1 (2006).</p>
+ * Transactions on Mathematical Software, 32, 1 (2006). The errata for the paper
+ * are in <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt">wellrng-errata.txt</a>.</p>
* @see <a href="http://www.iro.umontreal.ca/~panneton/WELLRNG.html">WELL Random number generator</a>
* @version $Revision$ $Date$
@@ -91,6 +92,7 @@ public class Well44497b extends Abstract
final int vM2 = v[i2[index]];
final int vM3 = v[i3[index]];
+ // the values below include the errata of the original article
final int z0 = (0xFFFF8000 & v[indexRm1]) ^ (0x00007FFF & v[indexRm2]);
final int z1 = (v0 ^ (v0 << 24)) ^ (vM1 ^ (vM1 >>> 30));
final int z2 = (vM2 ^ (vM2 << 10)) ^ (vM3 << 26);
@@ -101,7 +103,7 @@ public class Well44497b extends Abstract
v[index] = z3;
v[indexRm1] = z4;
- v[indexRm2] &= mp;
+ v[indexRm2] &= 0xFFFF8000;
index = indexRm1;
// add Matsumoto-Kurita tempering
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well512a.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well512a.java?rev=999577&r1=999576&r2=999577&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well512a.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/Well512a.java Tue Sep 21 19:50:43 2010
@@ -24,7 +24,8 @@ package org.apache.commons.math.random;
* Pierre L'Ecuyer and Makoto Matsumoto <a
* href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf">Improved
* Long-Period Generators Based on Linear Recurrences Modulo 2</a> ACM
- * Transactions on Mathematical Software, 32, 1 (2006).</p>
+ * Transactions on Mathematical Software, 32, 1 (2006). The errata for the paper
+ * are in <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt">wellrng-errata.txt</a>.</p>
* @see <a href="http://www.iro.umontreal.ca/~panneton/WELLRNG.html">WELL Random number generator</a>
* @version $Revision$ $Date$
@@ -87,8 +88,8 @@ public class Well512a extends AbstractWe
final int vi1 = v[i1[index]];
final int vi2 = v[i2[index]];
final int z0 = v[indexRm1];
- // m3: x ^ ((t >= 0) ? (x >>> t) : (x << -t));
+ // the values below include the errata of the original article
final int z1 = (vi ^ (vi << 16)) ^ (vi1 ^ (vi1 << 15));
final int z2 = vi2 ^ (vi2 >>> 11);
final int z3 = z1 ^ z2;
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/package.html
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/package.html?rev=999577&r1=999576&r2=999577&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/package.html (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/random/package.html Tue Sep 21 19:50:43 2010
@@ -16,5 +16,117 @@
limitations under the License.
-->
<!-- $Revision$ $Date$ -->
- <body>Random number and random data generators.</body>
+ <body>
+ <p>Random number and random data generators.</p>
+ <p>Commons-math provides a few pseudo random number generators. The top level interface is RandomGenerator.
+ It is implemented by three classes:
+ <ul>
+ <li>{@link org.apache.commons.math.random.JDKRandomGenerator JDKRandomGenerator}
+ that extends the JDK provided generator</li>
+ <li>AbstractRandomGenerator as a helper for users generators</li>
+ <li>BitStreamGenerator which is an abstract class for several generators and
+ which in turn is extended by:
+ <ul>
+ <li>{@link org.apache.commons.math.random.MersenneTwister MersenneTwister}</li>
+ <li>{@link org.apache.commons.math.random.Well512a Well512a}</li>
+ <li>{@link org.apache.commons.math.random.Well1024a Well1024a}</li>
+ <li>{@link org.apache.commons.math.random.Well19937a Well19937a}</li>
+ <li>{@link org.apache.commons.math.random.Well19937c Well19937c}</li>
+ <li>{@link org.apache.commons.math.random.Well44497a Well44497a}</li>
+ <li>{@link org.apache.commons.math.random.Well44497b Well44497b}</li>
+ </ul>
+ </li>
+ </ul>
+ </p>
+
+ <p>
+ The JDK provided generator is a simple one that can be used only for very simple needs.
+ The Mersenne Twister is a fast generator with very good properties well suited for
+ Monte-Carlo simulation. It is equidistributed for generating vectors up to dimension 623
+ and has a huge period: 2<sup>19937</sup> - 1 (which is a Mersenne prime). This generator
+ is described in a paper by Makoto Matsumoto and Takuji Nishimura in 1998: <a
+ href="http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf">Mersenne Twister:
+ A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator</a>, ACM
+ Transactions on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3--30.
+ The WELL generators are a family of generators with period ranging from 2<sup>512</sup> - 1
+ to 2<sup>44497</sup> - 1 (this last one is also a Mersenne prime) with even better properties
+ than Mersenne Twister. These generators are described in a paper by François Panneton,
+ Pierre L'Ecuyer and Makoto Matsumoto <a
+ href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf">Improved Long-Period
+ Generators Based on Linear Recurrences Modulo 2</a> ACM Transactions on Mathematical Software,
+ 32, 1 (2006). The errata for the paper are in <a
+ href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt">wellrng-errata.txt</a>.
+ </p>
+
+ <p>
+ For simple sampling, any of these generators is sufficient. For Monte-Carlo simulations the
+ JDK generator does not have any of the good mathematical properties of the other generators,
+ so it should be avoided. The Mersenne twister and WELL generators have equidistribution properties
+ proven according to their bits pool size which is directly linked to their period (all of them
+ have maximal period, i.e. a generator with size n pool has a period 2<sup>n</sup>-1). They also
+ have equidistribution properties for 32 bits blocks up to s/32 dimension where s is their pool size.
+ So WELL19937c for exemple is equidistributed up to dimension 623 (19937/32). This means a Monte-Carlo
+ simulation generating a vector of n variables at each iteration has some guarantees on the properties
+ of the vector as long as its dimension does not exceed the limit. However, since we use bits from two
+ successive 32 bits generated integers to create one double, this limit is smaller when the variables are
+ of type double. so for Monte-Carlo simulation where less the 16 doubles are generated at each round,
+ WELL1024 may be sufficient. If a larger number of doubles are needed a generator with a larger pool
+ would be useful.
+ </p>
+
+ <p>
+ The WELL generators are more modern then MersenneTwister (the paper describing than has been published
+ in 2006 instead of 1998) and fix some of its (few) drawbacks. If initialization array contains many
+ zero bits, MersenneTwister may take a very long time (several hundreds of thousands of iterations to
+ reach a steady state with a balanced number of zero and one in its bits pool). So the WELL generators
+ are better to <i>escape zeroland</i> as explained by the WELL generators creators. The Well19937a and
+ Well44497a generator are not maximally equidistributed (i.e. there are some dimensions or bits blocks
+ size for which they are not equidistributed). The Well512a, Well1024a, Well19937c and Well44497b are
+ maximally equidistributed for blocks size up to 32 bits (they should behave correctly also for double
+ based on more than 32 bits blocks, but equidistribution is not proven at these blocks sizes).
+ </p>
+
+ <p>
+ The MersenneTwister generator uses a 624 elements integer array, so it consumes less than 2.5 kilobytes.
+ The WELL generators use 6 integer arrays with a size equal to the pool size, so for example the
+ WELL44497b generator uses about 33 kilobytes. This may be important if a very large number of
+ generator instances were used at the same time.
+ </p>
+
+ <p>
+ All generators are quite fast. As an example, here are some comparisons, obtained on a 64 bits JVM on a
+ linux computer with a 2008 processor (AMD phenom Quad 9550 at 2.2 GHz). The generation rate for
+ MersenneTwister was about 27 millions doubles per second (remember we generate two 32 bits integers for
+ each double). Generation rates for other PRNG, relative to MersenneTwister:
+ </p>
+
+ <p>
+ <table border="1" align="center">
+ <tr BGCOLOR="#CCCCFF"><td colspan="2"><font size="+2">Example of performances</font></td></tr>
+ <tr BGCOLOR="#EEEEFF"><font size="+1"><td>Name</td><td>generation rate (relative to MersenneTwister)</td></font></tr>
+ <tr><td>{@link org.apache.commons.math.random.MersenneTwister MersenneTwister}</td><td>1</td></tr>
+ <tr><td>{@link org.apache.commons.math.random.JDKRandomGenerator JDKRandomGenerator}</td><td>between 0.96 and 1.16</td></tr>
+ <tr><td>{@link org.apache.commons.math.random.Well512a Well512a}</td><td>between 0.85 and 0.88</td></tr>
+ <tr><td>{@link org.apache.commons.math.random.Well1024a Well1024a}</td><td>between 0.63 and 0.73</td></tr>
+ <tr><td>{@link org.apache.commons.math.random.Well19937a Well19937a}</td><td>between 0.70 and 0.71</td></tr>
+ <tr><td>{@link org.apache.commons.math.random.Well19937c Well19937c}</td><td>between 0.57 and 0.71</td></tr>
+ <tr><td>{@link org.apache.commons.math.random.Well44497a Well44497a}</td><td>between 0.69 and 0.71</td></tr>
+ <tr><td>{@link org.apache.commons.math.random.Well44497b Well44497b}</td><td>between 0.65 and 0.71</td></tr>
+ </table>
+ </p>
+
+ <p>
+ So for most simulation problems, the better generators like {@link
+ org.apache.commons.math.random.Well19937c Well19937c} and {@link
+ org.apache.commons.math.random.Well44497b Well44497b} are probably very good choices.
+ </p>
+
+ <p>
+ Note that <em>none</em> of these generators are suitable for cryptography. They are devoted
+ to simulation, and to generate very long series with strong properties on the series as a whole
+ (equidistribution, no correlation ...). They do not attempt to create small series but with
+ very strong properties of unpredictability as needed in cryptography.
+ </p>
+
+ </body>
</html>
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=999577&r1=999576&r2=999577&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/changes.xml Tue Sep 21 19:50:43 2010
@@ -71,7 +71,7 @@ The <action> type attribute can be add,u
</action>
</release>
<release version="2.2" date="TBD" description="TBD">
- <action dev="luc" type="add" >
+ <action dev="luc" type="add" issue="MATH-419">
Added new random number generators from the Well Equidistributed Long-period Linear (WELL).
</action>
<action dev="psteitz" type="update" issue="MATH-409">
Modified: commons/proper/math/trunk/src/site/xdoc/userguide/random.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/site/xdoc/userguide/random.xml?rev=999577&r1=999576&r2=999577&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/userguide/random.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/userguide/random.xml Tue Sep 21 19:50:43 2010
@@ -317,6 +317,120 @@ for (int i = 0; i < 1000; i++) {
<code>java.util.Random</code> and wraps and delegates calls to
a <code>RandomGenerator</code> instance.
</p>
+
+ <p>Commons-math provides by itself several implementations of the <a
+ href="../apidocs/org/apache/commons/math/random/RandomGenerator.html">
+ RandomGenerator</a> interface:
+ <ul>
+ <li><a href="../apidocs/org/apache/commons/math/random/JDKRandomGenerator.html">JDKRandomGenerator</a>
+ that extends the JDK provided generator</li>
+ <li><a href="../apidocs/org/apache/commons/math/random/AbstractRandomGenerator.html">
+ AbstractRandomGenerator</a> as a helper for users generators</li>
+ <li><a href="../apidocs/org/apache/commons/math/random/BitStreamGenerator.html">
+ BitStreamGenerator</a> which is an abstract class for several generators and
+ which in turn is extended by:
+ <ul>
+ <li><a href="../apidocs/org/apache/commons/math/random/MersenneTwister.html">MersenneTwister</a></li>
+ <li><a href="../apidocs/org/apache/commons/math/random/Well512a.html">Well512a</a></li>
+ <li><a href="../apidocs/org/apache/commons/math/random/Well1024a.html">Well1024a</a></li>
+ <li><a href="../apidocs/org/apache/commons/math/random/Well19937a.html">Well19937a</a></li>
+ <li><a href="../apidocs/org/apache/commons/math/random/Well19937c.html">Well19937c</a></li>
+ <li><a href="../apidocs/org/apache/commons/math/random/Well44497a.html">Well44497a</a></li>
+ <li><a href="../apidocs/org/apache/commons/math/random/Well44497b.html">Well44497b</a></li>
+ </ul>
+ </li>
+ </ul>
+ </p>
+
+ <p>
+ The JDK provided generator is a simple one that can be used only for very simple needs.
+ The Mersenne Twister is a fast generator with very good properties well suited for
+ Monte-Carlo simulation. It is equidistributed for generating vectors up to dimension 623
+ and has a huge period: 2<sup>19937</sup> - 1 (which is a Mersenne prime). This generator
+ is described in a paper by Makoto Matsumoto and Takuji Nishimura in 1998: <a
+ href="http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf">Mersenne Twister:
+ A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator</a>, ACM
+ Transactions on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3--30.
+ The WELL generators are a family of generators with period ranging from 2<sup>512</sup> - 1
+ to 2<sup>44497</sup> - 1 (this last one is also a Mersenne prime) with even better properties
+ than Mersenne Twister. These generators are described in a paper by François Panneton,
+ Pierre L'Ecuyer and Makoto Matsumoto <a
+ href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf">Improved Long-Period
+ Generators Based on Linear Recurrences Modulo 2</a> ACM Transactions on Mathematical Software,
+ 32, 1 (2006). The errata for the paper are in <a
+ href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt">wellrng-errata.txt</a>.
+ </p>
+
+ <p>
+ For simple sampling, any of these generators is sufficient. For Monte-Carlo simulations the
+ JDK generator does not have any of the good mathematical properties of the other generators,
+ so it should be avoided. The Mersenne twister and WELL generators have equidistribution properties
+ proven according to their bits pool size which is directly linked to their period (all of them
+ have maximal period, i.e. a generator with size n pool has a period 2<sup>n</sup>-1). They also
+ have equidistribution properties for 32 bits blocks up to s/32 dimension where s is their pool size.
+ So WELL19937c for exemple is equidistributed up to dimension 623 (19937/32). This means a Monte-Carlo
+ simulation generating a vector of n variables at each iteration has some guarantees on the properties
+ of the vector as long as its dimension does not exceed the limit. However, since we use bits from two
+ successive 32 bits generated integers to create one double, this limit is smaller when the variables are
+ of type double. so for Monte-Carlo simulation where less the 16 doubles are generated at each round,
+ WELL1024 may be sufficient. If a larger number of doubles are needed a generator with a larger pool
+ would be useful.
+ </p>
+
+ <p>
+ The WELL generators are more modern then MersenneTwister (the paper describing than has been published
+ in 2006 instead of 1998) and fix some of its (few) drawbacks. If initialization array contains many
+ zero bits, MersenneTwister may take a very long time (several hundreds of thousands of iterations to
+ reach a steady state with a balanced number of zero and one in its bits pool). So the WELL generators
+ are better to <i>escape zeroland</i> as explained by the WELL generators creators. The Well19937a and
+ Well44497a generator are not maximally equidistributed (i.e. there are some dimensions or bits blocks
+ size for which they are not equidistributed). The Well512a, Well1024a, Well19937c and Well44497b are
+ maximally equidistributed for blocks size up to 32 bits (they should behave correctly also for double
+ based on more than 32 bits blocks, but equidistribution is not proven at these blocks sizes).
+ </p>
+
+ <p>
+ The MersenneTwister generator uses a 624 elements integer array, so it consumes less than 2.5 kilobytes.
+ The WELL generators use 6 integer arrays with a size equal to the pool size, so for example the
+ WELL44497b generator uses about 33 kilobytes. This may be important if a very large number of
+ generator instances were used at the same time.
+ </p>
+
+ <p>
+ All generators are quite fast. As an example, here are some comparisons, obtained on a 64 bits JVM on a
+ linux computer with a 2008 processor (AMD phenom Quad 9550 at 2.2 GHz). The generation rate for
+ MersenneTwister was between 25 and 27 millions doubles per second (remember we generate two 32 bits integers for
+ each double). Generation rates for other PRNG, relative to MersenneTwister:
+ </p>
+
+ <p>
+ <table border="1" align="center">
+ <tr BGCOLOR="#CCCCFF"><td colspan="2"><font size="+2">Example of performances</font></td></tr>
+ <tr BGCOLOR="#EEEEFF"><font size="+1"><td>Name</td><td>generation rate (relative to MersenneTwister)</td></font></tr>
+ <tr><td><a href="../apidocs/org/apache/commons/math/random/MersenneTwister.html">MersenneTwister</a></td><td>1</td></tr>
+ <tr><td><a href="../apidocs/org/apache/commons/math/random/JDKRandomGenerator.html">JDKRandomGenerator</a></td><td>between 0.96 and 1.16</td></tr>
+ <tr><td><a href="../apidocs/org/apache/commons/math/random/Well512a.html">Well512a</a></td><td>between 0.85 and 0.88</td></tr>
+ <tr><td><a href="../apidocs/org/apache/commons/math/random/Well1024a.html">Well1024a</a></td><td>between 0.63 and 0.73</td></tr>
+ <tr><td><a href="../apidocs/org/apache/commons/math/random/Well19937a.html">Well19937a</a></td><td>between 0.70 and 0.71</td></tr>
+ <tr><td><a href="../apidocs/org/apache/commons/math/random/Well19937c.html">Well19937c</a></td><td>between 0.57 and 0.71</td></tr>
+ <tr><td><a href="../apidocs/org/apache/commons/math/random/Well44497a.html">Well44497a</a></td><td>between 0.69 and 0.71</td></tr>
+ <tr><td><a href="../apidocs/org/apache/commons/math/random/Well44497b.html">Well44497b</a></td><td>between 0.65 and 0.71</td></tr>
+ </table>
+ </p>
+
+ <p>
+ So for most simulation problems, the better generators like <a
+ href="../apidocs/org/apache/commons/math/random/Well19937c.html">Well19937c</a> and <a
+ href="../apidocs/org/apache/commons/math/random/Well44497b.html">Well44497b</a> are probably very good choices.
+ </p>
+
+ <p>
+ Note that <em>none</em> of these generators are suitable for cryptography. They are devoted
+ to simulation, and to generate very long series with strong properties on the series as a whole
+ (equidistribution, no correlation ...). They do not attempt to create small series but with
+ very strong properties of unpredictability as needed in cryptography.
+ </p>
+
<p>
Examples:
<dl>