// ============================================================================
// Copyright 2006-2012 Daniel W. Dyer
//
// Licensed 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.uncommons.maths.random;
import java.util.Random;
import java.util.concurrent.locks.ReentrantLock;
import org.uncommons.maths.binary.BinaryUtils;
/**
* Random number generator based on the
* Mersenne
* Twister algorithm developed by Makoto Matsumoto and Takuji Nishimura.
*
* This is a very fast random number generator with good statistical
* properties (it passes the full DIEHARD suite). This is the best RNG
* for most experiments. If a non-linear generator is required, use
* the slower {@link AESCounterRNG} RNG.
*
* This PRNG is deterministic, which can be advantageous for testing purposes
* since the output is repeatable. If multiple instances of this class are created
* with the same seed they will all have identical output.
*
* This code is translated from the original C version and assumes that we
* will always seed from an array of bytes. I don't pretend to know the
* meanings of the magic numbers or how it works, it just does.
*
* NOTE: Because instances of this class require 128-bit seeds, it is not
* possible to seed this RNG using the {@link #setSeed(long)} method inherited
* from {@link Random}. Calls to this method will have no effect.
* Instead the seed must be set by a constructor.
*
* @author Makoto Matsumoto and Takuji Nishimura (original C version)
* @author Daniel Dyer (Java port)
*/
public class MersenneTwisterRNG extends Random implements RepeatableRNG
{
// The actual seed size isn't that important, but it should be a multiple of 4.
private static final int SEED_SIZE_BYTES = 16;
// Magic numbers from original C version.
private static final int N = 624;
private static final int M = 397;
private static final int[] MAG01 = {0, 0x9908b0df};
private static final int UPPER_MASK = 0x80000000;
private static final int LOWER_MASK = 0x7fffffff;
private static final int BOOTSTRAP_SEED = 19650218;
private static final int BOOTSTRAP_FACTOR = 1812433253;
private static final int SEED_FACTOR1 = 1664525;
private static final int SEED_FACTOR2 = 1566083941;
private static final int GENERATE_MASK1 = 0x9d2c5680;
private static final int GENERATE_MASK2 = 0xefc60000;
private final byte[] seed;
// Lock to prevent concurrent modification of the RNG's internal state.
private final ReentrantLock lock = new ReentrantLock();
private final int[] mt = new int[N]; // State vector.
private int mtIndex = 0; // Index into state vector.
/**
* Creates a new RNG and seeds it using the default seeding strategy.
*/
public MersenneTwisterRNG()
{
this(DefaultSeedGenerator.getInstance().generateSeed(SEED_SIZE_BYTES));
}
/**
* Seed the RNG using the provided seed generation strategy.
* @param seedGenerator The seed generation strategy that will provide
* the seed value for this RNG.
* @throws SeedException If there is a problem generating a seed.
*/
public MersenneTwisterRNG(SeedGenerator seedGenerator) throws SeedException
{
this(seedGenerator.generateSeed(SEED_SIZE_BYTES));
}
/**
* Creates an RNG and seeds it with the specified seed data.
* @param seed The seed data used to initialise the RNG.
*/
public MersenneTwisterRNG(byte[] seed)
{
if (seed == null || seed.length != SEED_SIZE_BYTES)
{
throw new IllegalArgumentException("Mersenne Twister RNG requires a 128-bit (16-byte) seed.");
}
this.seed = seed.clone();
int[] seedInts = BinaryUtils.convertBytesToInts(this.seed);
// This section is translated from the init_genrand code in the C version.
mt[0] = BOOTSTRAP_SEED;
for (mtIndex = 1; mtIndex < N; mtIndex++)
{
mt[mtIndex] = (BOOTSTRAP_FACTOR
* (mt[mtIndex - 1] ^ (mt[mtIndex - 1] >>> 30))
+ mtIndex);
}
// This section is translated from the init_by_array code in the C version.
int i = 1;
int j = 0;
for (int k = Math.max(N, seedInts.length); k > 0; k--)
{
mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >>> 30)) * SEED_FACTOR1)) + seedInts[j] + j;
i++;
j++;
if (i >= N)
{
mt[0] = mt[N - 1];
i = 1;
}
if (j >= seedInts.length)
{
j = 0;
}
}
for (int k = N - 1; k > 0; k--)
{
mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >>> 30)) * SEED_FACTOR2)) - i;
i++;
if (i >= N)
{
mt[0] = mt[N - 1];
i = 1;
}
}
mt[0] = UPPER_MASK; // Most significant bit is 1 - guarantees non-zero initial array.
}
/**
* {@inheritDoc}
*/
public byte[] getSeed()
{
return seed.clone();
}
/**
* {@inheritDoc}
*/
@Override
protected final int next(int bits)
{
int y;
try
{
lock.lock();
if (mtIndex >= N) // Generate N ints at a 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];
mtIndex = 0;
}
y = mt[mtIndex++];
}
finally
{
lock.unlock();
}
// Tempering
y ^= (y >>> 11);
y ^= (y << 7) & GENERATE_MASK1;
y ^= (y << 15) & GENERATE_MASK2;
y ^= (y >>> 18);
return y >>> (32 - bits);
}
}
Ads help maintain this website.