Mersenne Twister

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
gel
Posts: 28
Joined: May 27, 2005 22:50
Location: WA, USA

Mersenne Twister

Postby gel » Apr 29, 2006 6:28

I translated the Mersenne Twister random number generator from C. The original C code is here:

Mersenne Twister Homepage

The output matches the output of the C program, that is all of the testing I have done.

Code: Select all

'/*
'   A C-program for MT19937, with initialization improved 2002/1/26.
'   Coded by Takuji Nishimura and Makoto Matsumoto.
'
'   Before using, initialize the state by using init_genrand(seed) 
'   or init_by_array(init_key, key_length).
'
'   Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
'   All rights reserved.                         
'
'   Redistribution and use in source and binary forms, with or without
'   modification, are permitted provided that the following conditions
'   are met:
'
'     1. Redistributions of source code must retain the above copyright
'        notice, this list of conditions and the following disclaimer.
'
'     2. Redistributions in binary form must reproduce the above copyright
'        notice, this list of conditions and the following disclaimer in the
'        documentation and/or other materials provided with the distribution.
'
'     3. The names of its contributors may not be used to endorse or promote
'        products derived from this software without specific prior written
'        permission.
'
'   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
'   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
'   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
'   A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
'   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
'   EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
'   PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
'   PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
'   LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
'   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
'   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
'
'
'   Any feedback is very welcome.
'   http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
'   email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space)
'*/
'
' Translated to FreeBASIC by Greg Lyon - April 2006
'
Option Explicit
Option Base 0       
'
'#include <stdio.h>     
#Include "vbcompat.bi"

Declare Function main() As Long
'
'/* Period parameters */ 
'#define N 624
'#define M 397
'#define MATRIX_A 0x9908b0dfUL   /* constant vector a */
'#define UPPER_MASK 0x80000000UL /* most significant w-r bits */
'#define LOWER_MASK 0x7fffffffUL /* least significant r bits */   
'
Const N As uInteger = 624
Const M As uInteger = 397
Const MATRIX_A   As uInteger = &H9908b0dfUL ' constant vector a
Const UPPER_MASK As uInteger = &H80000000UL ' most significant w-r bits
Const LOWER_MASK As uInteger = &H7fffffffUL ' least significant r bits
'
'static unsigned long mt[N]; /* the array for the state vector  */
'static int mti=N+1; /* mti==N+1 means mt[N] is not initialized */
'
Dim Shared mt(N) As uInteger ' the array For the state vector
Dim Shared mti As Long = N + 1 ' mti == N+1 means mt[N] Is Not initialized   

main()
GetKey
End 0           

'
'-------------------------------------------------------
'/* initializes mt[N] with a seed */
'void init_genrand(unsigned long s)
'{
'    mt[0]= s & 0xffffffffUL;
'    for (mti=1; mti<N; mti++) {
'        mt[mti] =
'       (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
'        /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
'        /* In the previous versions, MSBs of the seed affect   */
'        /* only MSBs of the array mt[].                        */
'        /* 2002/01/09 modified by Makoto Matsumoto             */
'        mt[mti] &= 0xffffffffUL;
'        /* for >32 bit machines */
'    }
'}                   
' initializes mt[N] with a seed
Sub init_genrand(ByVal s As uInteger)
    mt(0)= s And &HffffffffUL
    For mti = 1 To N-1
         mt(mti) = ( 1812433253UL * ( mt(mti-1) Xor ( mt(mti-1) Shr 30 ) ) + mti )
        ' See Knuth TAOCP Vol2. 3rd Ed. P.106 For multiplier.
        ' In the previous versions, MSBs of the seed affect 
        ' only MSBs of the array mt[].                       
        ' 2002/01/09 modified by Makoto Matsumoto           
        mt(mti) = mt(mti) And &HffffffffUL
        ' For >32 Bit machines
    Next mti
End Sub
'-------------------------------------------------------
'/* initialize by an array with array-length */
'/* init_key is the array for initializing keys */
'/* key_length is its length */
'/* slight change for C++, 2004/2/26 */
'void init_by_array(unsigned long init_key[], int key_length)
'{
'    int i, j, k;
'    init_genrand(19650218UL);
'    i=1; j=0;
'    k = (N>key_length ? N : key_length);
'    for (; k; k--) {
'        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL))
'          + init_key[j] + j; /* non linear */
'        mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
'        i++; j++;
'        if (i>=N) { mt[0] = mt[N-1]; i=1; }
'        if (j>=key_length) j=0;
'    }
'    for (k=N-1; k; k--) {
'        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL))
'          - i; /* non linear */
'        mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
'        i++;
'        if (i>=N) { mt[0] = mt[N-1]; i=1; }
'    }
'
'    mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */
'}                       
'
' initialize by an array with array-length
' init_key is the array for initializing keys
' key_length is its length
' slight change for C++, 2004/2/26
Sub init_by_array(init_key() As uInteger, ByVal key_length As uInteger)

     Dim i As Long
     Dim j As Long
     Dim k As Long
     
     init_genrand(19650218UL)
     i = 1
     j = 0           
     k = IIf(N > key_length, N, key_length)
     For k = k To 1 Step -1
         mt(i) = (mt(i) Xor ((mt(i-1) Xor (mt(i-1) Shr 30)) * 1664525UL)) + init_key(j) + j ' non linear
         mt(i) = mt(i) And &HffffffffUL ' for WORDSIZE > 32 machines */
         i = i + 1
         j = j + 1
         If i >= N Then
             mt(0) = mt(N-1)
             i = 1
         End If
         If j >= key_length Then
            j = 0
         End If
     Next
     For k = N-1 To 1 Step -1
         mt(i) = (mt(i) Xor ((mt(i-1) Xor (mt(i-1) Shr 30)) * 1566083941UL)) - i ' non linear
         mt(i) = mt(i) And &HffffffffUL ' for WORDSIZE > 32 machines
         i = i + 1
         If i >= N Then
            mt(0) = mt(N-1)
            i = 1
         End If
     Next

     mt(0) = &H80000000UL ' MSB is 1; assuring non-zero initial array
     
End Sub
'-------------------------------------------------------
'/* generates a random number on [0,0xffffffff]-interval */
'unsigned long genrand_int32(void)
'{
'    unsigned long y;
'    static unsigned long mag01[2]={0x0UL, MATRIX_A};
'    /* mag01[x] = x * MATRIX_A  for x=0,1 */
'
'    if (mti >= N) { /* generate N words at one time */
'        int kk;
'
'        if (mti == N+1)   /* if init_genrand() has not been called, */
'            init_genrand(5489UL); /* a default initial seed is used */
'
'        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 & 0x1UL];
'        }
'        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 & 0x1UL];
'        }
'        y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
'        mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];
'
'        mti = 0;
'    }

'    y = mt[mti++];
'
'    /* Tempering */
'    y ^= (y >> 11);
'    y ^= (y << 7) & 0x9d2c5680UL;
'    y ^= (y << 15) & 0xefc60000UL;
'    y ^= (y >> 18);
'
'    return y;
'}
'
' generates a Random number On [0,0xffffffff]-interval
Function genrand_int32() As UInteger

    Dim y As UInteger
    Dim mag01(2) As uInteger => {&H0UL, MATRIX_A}   
   
    ' mag01[x] = x * MATRIX_A  For x=0,1

    If mti >= N Then
       ' generate N words at one Time
        Dim kk As Long

        If mti = N + 1 Then  ' If init_genrand() has Not been called,
            init_genrand(5489UL) ' a default initial seed Is used
        End If
       
        For kk = 0 To (N-M)-1
            y = (mt(kk) And UPPER_MASK) Or (mt(kk+1) And LOWER_MASK)
            mt(kk) = mt(kk+M) Xor (y Shr 1) Xor mag01(y And &H1UL)
        Next
       
        For kk = kk To (N-1)-1
            y = (mt(kk) And UPPER_MASK)Or (mt(kk+1) And LOWER_MASK)
            mt(kk) = mt(kk + (M-N)) Xor (y Shr 1) Xor mag01(y And &H1UL)
        Next
       
        y = (mt(N-1) And UPPER_MASK) Or (mt(0) And LOWER_MASK)
        mt(N-1) = mt(M-1) Xor (y Shr 1) Xor mag01(y And &H1UL)

        mti = 0
       
    End If
 
    y = mt(mti)
    mti = mti + 1

    ' Tempering
    y = y Xor (y Shr 11)   
    y = y Xor ((y Shl  7) And &H9d2c5680UL)
    y = y Xor ((y Shl 15) And &Hefc60000UL)
    y = y Xor (y Shr 18)

    Function = y
   
End Function
'-------------------------------------------------------
'/* generates a random number on [0,0x7fffffff]-interval */
'long genrand_int31(void)
'{
'    return (long)(genrand_int32()>>1);
'}       
'
' generates a random number on [0,0x7fffffff]-interval
Function genrand_int31() As Long
    Function = CLng(genrand_int32() Shr 1)
End Function
'-------------------------------------------------------
'/* generates a random number on [0,1]-real-interval */
'double genrand_real1(void)
'{
'    return genrand_int32()*(1.0/4294967295.0);
'    /* divided by 2^32-1 */
'}
'
' generates a random number on [0,1]-real-interval
Function genrand_real1() As Double
    Function = genrand_int32() * (1.0# / 4294967295.0#)
    ' divided by 2^32-1
End Function
'-------------------------------------------------------
'/* generates a random number on [0,1)-real-interval */
'double genrand_real2(void)
'{
'    return genrand_int32()*(1.0/4294967296.0);
'    /* divided by 2^32 */
'}
'
' generates a Random number On [0,1)-real-interval
Function genrand_real2() As Double
    Function = genrand_int32() * (1.0# / 4294967296.0#)
    ' divided by 2^32
End Function
'-------------------------------------------------------'
'/* generates a random number on (0,1)-real-interval */
'double genrand_real3(void)
'{
'    return (((double)genrand_int32()) + 0.5) * (1.0 / 4294967296.0);
'    /* divided by 2^32 */
'}
'
' generates a Random number On (0,1)-real-interval
Function genrand_real3() As Double
    Function =  (CDbl(genrand_int32()) + 0.5#) * (1.0# / 4294967296.0#)
    ' divided by 2^32
End Function
'-------------------------------------------------------
'/* generates a random number on [0,1) with 53-bit resolution*/
'double genrand_res53(void)
'{
'    unsigned long a=genrand_int32()>>5, b=genrand_int32()>>6;
'    return(a*67108864.0+b)*(1.0/9007199254740992.0);
'}
'/* These real versions are due to Isaku Wada, 2002/01/09 added */
'     
' generates a random number on [0,1) with 53-bit resolution
Function genrand_res53() As Double 
    Dim a As uInteger = genrand_int32() Shr 5
    Dim b As uInteger = genrand_int32() Shr 6

    Function = (a * 67108864.0# + b) * (1.0# / 9007199254740992.0#)
End Function
' These real versions are due to Isaku Wada, 2002/01/09 added
'-------------------------------------------------------
'int main(void)
'{
'    int i;
'    unsigned long init[4]={0x123, 0x234, 0x345, 0x456}, length=4;
'    init_by_array(init, length);
'    printf("1000 outputs of genrand_int32()\n");
'    for (i=0; i<1000; i++) {
'      printf("%10lu ", genrand_int32());
'      if (i%5==4) printf("\n");
'    }
'    printf("\n1000 outputs of genrand_real2()\n");
'    for (i=0; i<1000; i++) {
'      printf("%10.8f ", genrand_real2());
'      if (i%5==4) printf("\n");
'    }
'    return 0;
'}
'
Function main() As Long
    Dim i As Long
    Dim init(4) As uInteger => {&H123, &H234, &H345, &H456}
    Dim length As uInteger = 4
    init_by_array(init(), length)
    Print "1000 outputs of genrand_int32()"
    For i = 0 To 999
      Print Format$(genrand_int32(), "0000000000") & " ";
      If (i Mod 5) = 4 Then
        Print
      End If 
    Next   
    Print
    Print "1000 outputs of genrand_real2()"
    For i = 0 To 999
      Print Format$(genrand_real2(), "0.00000000") & " ";
      If (i Mod 5) = 4 Then
          Print
      End If   
    Next i
    Function = 0
End Function
'-------------------------------------------------------
Last edited by gel on Apr 29, 2006 22:10, edited 2 times in total.
jdebord
Posts: 529
Joined: May 27, 2005 6:20
Location: Limoges, France
Contact:

Postby jdebord » Apr 29, 2006 8:51

Excellent work! Thank you very much.

The Mersenne twister is considered to be one of the most reliable algorithms for generating random numbers.

I will try to test it with Marsaglia's DIEHARD program.

If you don't mind I will add it to my FBMath library (http://sourceforge.net/projects/fbmath/)
gel
Posts: 28
Joined: May 27, 2005 22:50
Location: WA, USA

Postby gel » Apr 29, 2006 15:40

jdebord,

Thanks. Feel free to do whatever you would like with it.

I touched it up a little this morning, just cosmetic stuff.
Antoni
Posts: 1393
Joined: May 27, 2005 15:40
Location: Barcelona, Spain

Postby Antoni » Apr 29, 2006 20:30

I did one speed test: it is 3 times slower than RND in Windows, but after reading the experts reviews the algorithm is worh the pain. Thanks, gel!
gel
Posts: 28
Joined: May 27, 2005 22:50
Location: WA, USA

Postby gel » Apr 29, 2006 20:43

Antoni,

It could be sped up with some inline assembly. There are versions in asm that are pretty darn fast.
jdebord
Posts: 529
Joined: May 27, 2005 6:20
Location: Limoges, France
Contact:

Postby jdebord » May 08, 2006 9:59

The MT generator has been added to the FBMath project. The new package is available at:

http://sourceforge.net/projects/fbmath/

This version gives you the choice between two generators: MT and MWC (Multiply-With-Carry). The second one is slightly faster but may be less reliable. However, both generators passed the DIEHARD tests.

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 6 guests