Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

Mersenne Twister - Random number generator

View MersenneTwister.scala
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
// Mersenne Twister 19937
// Based on code from: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
// Note: This implementation is not thread-safe!
final class MersenneTwister (seed: Int = 5489) {
private val N = 624
private val M = 397
 
private val MatrixA = 0x9908b0dfL
 
private val UpperMask = 0x80000000L
private val LowerMask = 0x7fffffffL
 
private val mt = new Array[Long](N)
private var mti = N + 1
 
mt(0) = seed
for (i <- 1 until N) mt(i) = (1812433253L * (mt(i - 1) ^ (mt(i - 1) >>> 30)) + i) & 0xffffffffL
 
// Generates the next random integer in the sequence
def nextInt(): Int = {
var y = 0L
 
if (mti >= N) {
val mag01 = Array(0L, MatrixA)
 
var kk = 0
while (kk < N - M) {
y = (mt(kk) & UpperMask) | (mt(kk + 1) & LowerMask)
mt(kk) = mt(kk + M) ^ (y >>> 1) ^ mag01(y.toInt & 0x1)
kk += 1
}
while (kk < N - 1) {
y = (mt(kk) & UpperMask) | (mt(kk + 1) & LowerMask)
mt(kk) = mt(kk + (M - N)) ^ (y >>> 1) ^ mag01(y.toInt & 0x1)
kk += 1
}
y = (mt(N - 1) & UpperMask) | (mt(0) & LowerMask)
mt(N - 1) = mt(M - 1) ^ (y >>> 1) ^ mag01(y.toInt & 0x1)
 
mti = 0
}
 
y = mt(mti); mti += 1
y ^= y >>> 11
y ^= (y << 7) & 0x9d2c5680L
y ^= (y << 15) & 0xefc60000L
y ^= (y >>> 18)
 
y.toInt
}
 
// Generates a random integer in the interval [0, limit)
def nextInt(limit: Int): Int = {
// Find shift distance
val lim = limit.toLong & 0xffffffffL
var n = -1; var bit = 1L << 32
while (bit > lim) { n += 1; bit >>>= 1 }
 
// Generate integer, take most significant bits; reject while outside interval
var r = (nextInt().toLong & 0xffffffffL) >>> n
while (r >= lim) { r = (nextInt().toLong & 0xffffffffL) >>> n }
r.toInt
}
 
// Generates a random Double in the interval [0, 1)
def nextDouble(): Double = {
val a: Long = (nextInt().toLong & 0xffffffffL) >>> 5
val b: Long = (nextInt().toLong & 0xffffffffL) >>> 6
(a * 67108864.0 + b) / 9007199254740992.0
}
}

In comparison to the reference you left out some 'and 0xffffffffL'. Is this correct and if yes, why?

Owner

Hello perian, my Scala source code is pretty much a straightforward translation of the function genrand_int32 in the C source code that you can find here: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c

A minor complication is that Scala doesn't have unsigned integer data types like C.
Can you indicate where exactly you see missing 'and 0xffffffffL' statements?

In your line 16 there is a difference to the referenced C-code.

Orignal: mt[0]= s & 0xffffffffUL;
Scala: mt(0) = seed

I am not quite sure if it is neccessary. It just realized it.

Owner

In the original code, the seed is an unsigned (64-bit) long, and the "& 0xffffffffUL" is done so that only the lower 32 bits of the seed are used. In my code, the seed is an Int, which is 32 bits. Since it's already 32 bits the "& 0xffffffff" isn't necessary. (It would have been better in the original C code to make the seed an unsigned (32-bit) int, but for some reason the author didn't choose to do this).

Thanks for clarification.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.