mersennetwister.java

经典的货郎担问题解决办法

/*
** This code was modestly modified and completely reformatted, by Kent
** Paul Dolan, from published code.  See accompanying file
** TravellerDoc.html for details, credits, and status of the
** modifications for your use.
*/

package com.well.www.user.xanthian.java.tools;

/*
** Because my opinions are brittle as old glass, and the last time they
** were flexible, I was still teething, this code has been reformatted
** to a coding style I like better and can read with eyes trained on
** Pascal and Fortran.  Except for commenting out the main routine
** included for testing, there shouldn't be any substantive changes,
** just whitespace changes, comment style changes, and optional brackets
** optioned-in wherever I caught them.  KPD.
** 
** Oops.  Now there are.  I added extra routines to match the ones in
** Scott Robert Ladd's "Randomizer" class.
** 
** I also provided the option to use the MersenneTwister as a Design
** Pattern "Solitary", with two getTwister accessor methods that create
** an instance only once, and a static member to hold the soliton, so
** that MersenneTwister as a class can own its own only instance, and
** thus remove the need for consumers to pass around a solitary instance
** as parameters or with accessor methods in creators for consumers.  By
** not making the constructors private, I left this as an option up to
** the self discipline of the programmer(s), rather than making such
** usage mandatory.
*/

import java.io.*;
import java.util.*;

/*
** <h3>Mersenne Twister and MersenneTwisterFast</h3>
**
** <p><b>Version 3</b>, based on version MT199937(99/10/29)
** of the Mersenne Twister algorithm found at <a
** href="http://www.math.keio.ac.jp/matumoto/emt.html">The Mersenne
** Twister Home Page</a>.  By Sean Luke, June 2000.
**
** <p><b>MersenneTwister</b> is a drop-in subclass replacement for
** java.util.Random.  It is properly synchronized and can be used in
** a multithreaded environment.
**
** <p><b>MersenneTwisterFast</b> is not a subclass of java.util.Random.
** It has the same public methods as Random does, however, and it is
** algorithmically identical to MersenneTwister.  MersenneTwisterFast
** has hard-code inlined all of its methods directly, and made all of
** them final (well, the ones of consequence anyway).  Further, these
** methods are <i>not</i> synchronized, so the same MersenneTwisterFast
** instance cannot be shared by multiple threads.  But all this helps
** MersenneTwisterFast achieve over twice the speed of MersenneTwister.
**
** <h3>About the Mersenne Twister</h3> <p>This is a Java version of
** the C-program for MT19937: Integer version.  The MT19937 algorithm
** was created by Makoto Matsumoto and Takuji Nishimura, who ask:
** "When you use this, send an email to: [e-mail]
** with an appropriate reference to your work".  Indicate that this
** is a translation of their algorithm into Java.
**
** <p><b>Reference. </b>
** Makato Matsumoto and Takuji Nishimura,
** "Mersenne Twister: A 623-Dimensionally Equidistributed Uniform
** Pseudo-Random Number Generator",
** <i>ACM Transactions on Modeling and Computer Simulation,</i>
** Vol. 8, No. 1, January 1998, pp 3--30.
**
** <h3>About this Version</h3>
** This version of the code implements the MT19937 Mersenne Twister
** algorithm, with the 99/10/29 seeding mechanism.  The original
** mechanism did not permit 0 as a seed, and odd numbers were not good
** seed choices.  The new version permits any 32-bit signed integer.
** This algorithm is identical to the MT19937 integer algorithm; real
** values conform to Sun's float and double random number generator
** standards rather than attempting to implement the half-open or
** full-open MT19937-1 and MT199937-2 algorithms.
**
** <p>This code is based on standard MT19937 C/C++ code by Takuji
** Nishimura, with suggestions from Topher Cooper and Marc Rieffel,
** July 1997.  The code was originally translated into Java by Michael
** Lecuyer, January 1999, and is Copyright (c) 1999 by Michael Lecuyer.
** The included license is as follows:
** <blockquote><font size="-1">
**
** The basic algorithmic work of this library (appearing in nextInt()
** and setSeed()) is free software; you can redistribute it and or
** modify it under the terms of the GNU Library General Public License
** as published by the Free Software Foundation; either version 2 of
** the License, or (at your option) any later version.
**
** <p>This library is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
** Library General Public License for more details.  You should have
** received a copy of the GNU Library General Public License along
** with this library; if not, write to the Free Foundation, Inc.,
** 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
**
** </font></blockquote>
**
** <h3>Bug Fixes</h3>
**
** <p>This implementation implements the bug fixes
** made in Java 1.2's version of Random, which means
** it can be used with earlier versions of Java.  See <a
** href="http://www.javasoft.com/products/jdk/1.2/docs/api/java/util/Random.html">
** the JDK 1.2 java.util.Random documentation</a> for further
** documentation on the random-number generation contracts
** made.  Additionally, there's an undocumented bug in the JDK
** java.util.Random.nextBytes() method, which this code fixes.
**
** <h3>Important Note on Seeds</h3>
**
** <p> Just like java.util.Random, this generator accepts a long
** seed but doesn't use all of it.  java.util.Random uses 48 bits.
** The Mersenne Twister instead uses 32 bits (int size).  So it's
** best if your seed does not exceed the int range.
**
** <h3>Timings On Different Java Versions</h3>
**
** <p>MersenneTwister can be used reliably on JDK version
** 1.1.5 or above.  Earlier Java versions have serious bugs in
** java.util.Random; only MersenneTwisterFast (and not MersenneTwister
** nor java.util.Random) should be used with them. And why would
** you use 'em anyway?  They're very slow, as you'll see.  Here are
** some timings in milliseconds on a Sun Creator3D/Ultra 60 running
** SunOS 5.6.
**
** <dl>
** <dt><i>Standard C Version (gcc -O2)</i>
** <dd>1070
**
** <dt><i>Standard C Version (Solaris cc -O)</i>
** <dd>1210
**
** <dt><i>JDK 1.2.2 w/Hotspot Compiler (-O)</i>
** <dd>MTF: 1785, MT: 3699, java.util.Random: 4849
**
** <dt><i>JDK 1.2.1/1.2.2 (-O)</i>
** <dd>MTF: 1827, MT: 3868, java.util.Random: 4194
**
** <dt><i>JDK 1.1.8 (-O)</i>
** <dd>MTF: 40509, MT: 45853, java.util.Random: 24604 <br>
** Beats me why it's so slow...
**
** <dt><i>JDK 1.1.5 (-O)</i>
** <dd>MTF: 4056, MT: 20478, java.util.Random: 19692
**
** <dt><i>JDK 1.0.2 (-O)</i>
**
** <dd>MTF: 71640, MT: 66176, java.util.Random: 67269 <br>
**
** <i>Important note:</i>  Do not MersenneTwister.java or
** java.util.Random on a Java version this early!  Random number
** generation in versions less than 1.1.5 has serious bugs.
** </dl>
   @version 3
*/

public class MersenneTwister extends java.util.Random implements Serializable
{

/*
** Turn this into a soliton; there's no real need to have more than one
** instance, and having it own its own only instance decouples it from
** instantiating routines, making it much easier to share.
*/
 
  private static MersenneTwister m_soliton = null;

  // Period parameters
  private static final int N = 624;
  private static final int M = 397;
  private static final int MATRIX_A = 0x9908b0df;   // private static final * constant vector a
  private static final int UPPER_MASK = 0x80000000; // most significant w-r bits
  private static final int LOWER_MASK = 0x7fffffff; // least significant r bits

  // Tempering parameters
  private static final int TEMPERING_MASK_B = 0x9d2c5680;
  private static final int TEMPERING_MASK_C = 0xefc60000;

  // #define TEMPERING_SHIFT_U(y)  (y >>> 11)
  // #define TEMPERING_SHIFT_S(y)  (y << 7)
  // #define TEMPERING_SHIFT_T(y)  (y << 15)
  // #define TEMPERING_SHIFT_L(y)  (y >>> 18)

  private int mt[]; // the array for the state vector
  private int mti; // mti==N+1 means mt[N] is not initialized
  private int mag01[];

  // a good initial seed (of int size, though stored in a long)
  private static final long GOOD_SEED = 4357;

/*
** Implemented here because there's a bug in Random's implementation
** of the Gaussian code (divide by zero, and log(0), ugh!), yet its
** gaussian variables are private so we can't access them here.  :-(
*/

  private double __nextNextGaussian;
  private boolean __haveNextNextGaussian;

/*
** Constructor using the default seed.
*/

  public MersenneTwister()
  {
    super(GOOD_SEED);  // just in case
    setSeed(GOOD_SEED);
  }

  public static synchronized MersenneTwister getTwister()
  {
    if ( m_soliton == null ) { m_soliton = new MersenneTwister(); }
    return m_soliton;
  }

/*
** Constructor using a given seed.  Though you pass this seed in as
** a long, it's best to make sure it's actually an integer.
*/

  public MersenneTwister(final long seed)
  {
    super(seed);    // just in case
    setSeed(seed);
  }

  public static MersenneTwister getTwister(final long seed)
  {

/*
** Notice that, as part of making this a soliton, the use that way of
** multiple constructor calls with different seeds goes away.  If the
** application is so disorganized it tries to seed the Twister multiple
** times, ignore subsequent attempts.  The intention is that the client
** application should create one instance in its setup procedings, and
** do any desired seeding there.
*/

    if ( m_soliton == null ) { m_soliton = new MersenneTwister(seed); }
    return m_soliton;
  }

/*
** Initalize the pseudo random number generator.  This is the old
** seed-setting mechanism for the original Mersenne Twister algorithm.
** You must not use 0 as your seed, and don't pass in a long that's
** bigger than an int (Mersenne Twister only uses the first 32 bits
** for its seed).  Also it's suggested that for you avoid even-numbered
** seeds in this older seed-generation procedure.
**
*/

  synchronized public void setSeedOld(final long seed)
  {

/*
** it's always good style to call super
*/

    super.setSeed(seed);

/*
** Due to a bug in java.util.Random clear up to 1.2, we're doing our
** own Gaussian variable.
*/

    __haveNextNextGaussian = false;

    mt = new int[N];

/*
** setting initial seeds to mt[N] using the generator Line 25 of
** Table 1 in [KNUTH 1981, The Art of Computer Programming Vol. 2
** (2nd Ed.), pp102]
**
** the 0xffffffff is commented out because in Java ints are always
** 32 bits; hence i & 0xffffffff == i
*/

    mt[0]= ((int)seed); // & 0xffffffff;

    for (mti = 1; mti < N; mti++)
    {
      mt[mti] = (69069 * mt[mti-1]); //& 0xffffffff;
    }

/*
**  mag01[x] = x * MATRIX_A  for x=0,1
*/

    mag01 = new int[2];
    mag01[0] = 0x0;
    mag01[1] = MATRIX_A;
  }


/*
** An alternative, more complete, method of seeding the pseudo random
** number generator.  array must be an array of 624 ints, and they
** can be any value as long as they're not *all* zero.
*/

  synchronized public void setSeed(final int[] array)
  {

/*
** it's always good style to call super -- we'll use MT's canonical
** random number, but it doesn't really matter.
*/
    super.setSeed(4357);

/*
**  Due to a bug in java.util.Random clear up to 1.2, we're/ doing
**  our own Gaussian variable.
*/

    __haveNextNextGaussian = false;

    mt = new int[N];
    System.arraycopy(array,0,mt,0,N);
    mti=N;
    // mag01[x] = x * MATRIX_A  for x=0,1
    mag01 = new int[2];
    mag01[0] = 0x0;
    mag01[1] = MATRIX_A;
  }


/*
** Initalize the pseudo random number generator.  Don't pass in a
** long that's bigger than an int (Mersenne Twister only uses the
** first 32 bits for its seed).
**
*/

  synchronized public void setSeed(final long seed)
  {

/*
** it's always good style to call super
*/

    super.setSeed(seed);

/*
** seed needs to be cast into an int first for this to work
*/

    int _seed = (int)seed;

/*
** Due to a bug in java.util.Random clear up to 1.2, we're doing our
** own Gaussian variable.
*/

    __haveNextNextGaussian = false;

    mt = new int[N];

    for (int i=0;i<N;i++)
    {
      mt[i] = _seed & 0xffff0000;
      _seed = 69069 * _seed + 1;
      mt[i] |= (_seed & 0xffff0000) >>> 16;
      _seed = 69069 * _seed + 1;
    }

    mti=N;
    // mag01[x] = x * MATRIX_A  for x=0,1
    mag01 = new int[2];
    mag01[0] = 0x0;
    mag01[1] = MATRIX_A;
  }



/*
** Returns an integer with <i>bits</i> bits filled with a random
** number.
*/

  synchronized protected int next(final int bits)
  {
    int y;

    if (mti >= N)   // generate N words at one time
    {
        int kk;

        for (kk = 0; kk < N - M; kk++)
        {
          y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
          mt[kk] = mt[kk+M] ^ (y >>> 1) ^ mag01[y & 0x1];
        }

        for (; kk < N-1; kk++)
        {
          y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
          mt[kk] = mt[kk+(M-N)] ^ (y >>> 1) ^ mag01[y & 0x1];
        }

        y = (mt[N-1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
        mt[N-1] = mt[M-1] ^ (y >>> 1) ^ mag01[y & 0x1];

        mti = 0;
    }

    y = mt[mti++];
    y ^= y >>> 11;                          // TEMPERING_SHIFT_U(y)
    y ^= (y << 7) & TEMPERING_MASK_B;       // TEMPERING_SHIFT_S(y)
    y ^= (y << 15) & TEMPERING_MASK_C;      // TEMPERING_SHIFT_T(y)
    y ^= (y >>> 18);                        // TEMPERING_SHIFT_L(y)

    return y >>> (32 - bits);    // hope that's right!
  }

/*
** If you've got a truly old version of Java, you can omit these two
** next methods.
*/

  private synchronized void writeObject(final ObjectOutputStream out)
    throws IOException
  {