Pseudo-Random Numbers, VB and Doing the (Mersenne) Twist…

Interesting how random things sometimes come together. I was checking out Chris William’s pre-beta rogue-like game Heroic Adventure! on CodePlex and noticed that although most of the game is written in VB, he had included some C# code in there. The motivation was the fact that the pseudo-random number generators that VB and the .NET platform provide (i.e. VB’s Rnd function and .NET’s System.Random) are not strong enough to satisfy the random number needs of his game. So he borrowed some C# code that implements the Mersenne Twister algorithm, which is a much better pseudo-random number generator.

I thought it was a shame for Chris to have to sully all his beautiful VB code with some C# (obligatory <g> for the humor impaired), so I took a look at the reference implementation of the algorithm and coded it up in VB (making sure, of course, the test output matched that of the reference implementation). For those of you with random number needs, I’ve attached it at the end. Please let me know if you find bugs.

Interestingly, at almost exactly the same time, the question of the strength (or lack thereof) of our pseudo-random number generator came up internally. Keep in mind that VB .NET’s Rnd function was written to remain completely compatible with VB 6.0’s Rnd function, which was compatible with VB 5.0’s Rnd function, etc., etc., all the way back to VB 1.0’s Rnd function. So that pseudo-random number generator is pretty freaking old — 15+ years and counting! We’re discussing what we might do about the situation, but since some people may depend on setting a particular seed and then getting a predictable sequence…

One caveat to keep in mind is that none of these pseudo-random number generators are strong enough to be used for cryptographic uses. For that, try System.Security.Cryptography.RNGCryptoServiceProvider.

'
' An implementation of the Mersenne Twister algorithm (MT19937), developed
' with reference to the C code written by Takuji Nishimura and Makoto Matsumoto
' (http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html).
'
' This code is free to use for any pupose.
'

Option Strict On

''' 
''' A random number generator with a uniform distribution using the Mersenne 
''' Twister algorithm.
''' 
Public Class MersenneTwister
    Private Const N As Integer = 624
    Private Const M As Integer = 397
    Private Const MATRIX_A As UInteger = &H9908B0DFUI
    Private Const UPPER_MASK As UInteger = &H80000000UI
    Private Const LOWER_MASK As UInteger = &H7FFFFFFFUI

    Private mt(N - 1) As UInteger
    Private mti As Integer = N + 1

    ''' 
    ''' Create a new Mersenne Twister random number generator.
    ''' 
    Public Sub New()
        Me.New(CUInt(Date.Now.Millisecond))
    End Sub

    ''' 
    ''' Create a new Mersenne Twister random number generator with a
    ''' particular seed.
    ''' 
    ''' The seed for the generator.
    Public Sub New(ByVal seed As UInteger)
        mt(0) = seed
        For mti = 1 To N - 1
            mt(mti) = CUInt((1812433253UL * (mt(mti - 1) Xor (mt(mti - 1) >> 30)) + CUInt(mti)) And &HFFFFFFFFUL)
        Next
    End Sub

    ''' 
    ''' Create a new Mersenne Twister random number generator with a
    ''' particular initial key.
    ''' 
    ''' The initial key.
    Public Sub New(ByVal initialKey() As UInteger)
        Me.New(19650218UI)

        Dim i, j, k As Integer
        i = 1 : j = 0
        k = CInt(IIf(N > initialKey.Length, N, initialKey.Length))

        For k = k To 1 Step -1
            mt(i) = CUInt(((mt(i) Xor ((mt(i - 1) Xor (mt(i - 1) >> 30)) * 1664525UL)) + initialKey(j) + CUInt(j)) And &HFFFFFFFFUI)
            i += 1 : j += 1
            If i >= N Then mt(0) = mt(N - 1) : i = 1
            If j >= initialKey.Length Then j = 0
        Next

        For k = N - 1 To 1 Step -1
            mt(i) = CUInt(((mt(i) Xor ((mt(i - 1) Xor (mt(i - 1) >> 30)) * 1566083941UL)) - CUInt(i)) And &HFFFFFFFFUI)
            i += 1
            If i >= N Then mt(0) = mt(N - 1) : i = 1
        Next

        mt(0) = &H80000000UI
    End Sub

    ''' 
    ''' Generates a random number between 0 and System.UInt32.MaxValue.
    ''' 
    Public Function GenerateUInt32() As UInteger
        Dim y As UInteger
        Static mag01() As UInteger = {&H0UI, MATRIX_A}

        If mti >= N Then
            Dim kk As Integer

            Debug.Assert(mti <> N + 1, "Failed initialization")

            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 >> 1) Xor mag01(CInt(y And &H1))
            Next

            For kk = kk To N - 2
                y = (mt(kk) And UPPER_MASK) Or (mt(kk + 1) And LOWER_MASK)
                mt(kk) = mt(kk + (M - N)) Xor (y >> 1) Xor mag01(CInt(y And &H1))
            Next

            y = (mt(N - 1) And UPPER_MASK) Or (mt(0) And LOWER_MASK)
            mt(N - 1) = mt(M - 1) Xor (y >> 1) Xor mag01(CInt(y And &H1))

            mti = 0
        End If

        y = mt(mti)
        mti += 1

        ' Tempering
        y = y Xor (y >> 11)
        y = y Xor ((y << 7) And &H9D2C5680UI)
        y = y Xor ((y << 15) And &HEFC60000UI)
        y = y Xor (y >> 18)

        Return y
    End Function

    ''' 
    ''' Generates a random integer between 0 and System.Int32.MaxValue.
    ''' 
    Public Function GenerateInt32() As Integer
        Return CInt(GenerateUInt32() >> 1)
    End Function

    ''' 
    ''' Generates a random integer between 0 and maxValue.
    ''' 
    ''' The maximum value. Must be greater than zero.
    Public Function GenerateInt32(ByVal maxValue As Integer) As Integer
        Return GenerateInt32(0, maxValue)
    End Function

    ''' 
    ''' Generates a random integer between minValue and maxValue.
    ''' 
    ''' The lower bound.
    ''' The upper bound.
    Public Function GenerateInt32(ByVal minValue As Integer, ByVal maxValue As Integer) As Integer
        Return CInt(Math.Floor((maxValue - minValue + 1) * GenerateDouble() + minValue))
    End Function

    ''' 
    ''' Generates a random floating point number between 0 and 1.
    ''' 
    Public Function GenerateDouble() As Double
        Return GenerateUInt32() * (1.0 / 4294967295.0)
    End Function
End Class

Updated 09/22/2006: The dingo ate my XML comments! Fixed.

Updated 09/22/2006 (Later): The dingo ate my <g> as well! Fixed.

12 thoughts on “Pseudo-Random Numbers, VB and Doing the (Mersenne) Twist…

  1. Anthony D. Green, MCTS

    Paul,

    This raises a question in my mind. How does the VB team decide when to abandon, support, or enhance legacy language features?

    How has experience changed the way you implement new features? Do you implement them in anticipation of one day changing them to take advanted of newer research and technology or even deprecating them?

    As an example, during Whidbey (been so long since I’ve said that) Beta I suggested revamping the Like operator to take advantage of language level Regular Expressions a la Perl and was told that the operator was being maintained only for backwards compatability and as such would keep its old behavior – fair enough. Clearly form the clamoring MVPs you have made tough choices on what to keep and what to kill in VB. I’m the first to admit that due to VB’s popularity, accessibility, and flexibility you have a large and heterogenous constituency with divergent interests. How do you reconcile these forces?

    Do you ever feel frustrated by the legacy baggage stiffling innovation? What would you say to the VB users (or former VB users) who see C# as a modern, RAD alternative to either VB or C++/CLI who both suffer in the extreme the weight of their own history? What would you say to the various sects within VB who perceive that the language is "being screwed over" by catering to other community segments? And to return to my original question, at what point is 15 years of consistent behavior of Rnd enough – how long should we support writing code in 1983 frozen-time-loop just because we did write code in 1983?

    Reply
  2. Branco Medeiros

    Glad you’re posting again about VB.

    I miss the ‘behind the scenes’ posts, where you used to talk about the design decisions that turned VB.Net into what it is today. Hope you return to the subject, which I find fascinating.

    One thing that makes me curious is the design decision to use ReadOnly/WriteOnly instead of the old-style Get/Set property declarations.

    I’d dare to suggest you to bring back the old style Property declaration, which can co-exist with the current approach; besides fiting nicely, it would eliminate the need to use Get and Set in the body of the procedure (less typing).

    Ex:

    ‘Normal Property:

    Property Age As Integer

    Get

    Return mAge

    End Get

    Set(ByVal Value As Integer)

    mAge = Value

    End Set

    End Property

    ‘ReadOnly Property

    Property Get Age As Integer

    Return mAge

    End Property

    ‘WriteOnly Property

    Property Set Age(ByVal Value As Integer)

    mAge = Value

    End Property

    Another suggestion would be to allow a short circuit syntax in field declarations meant to be just enclosed by properties:

    ‘A Read/Write field + property

    Private mAge As Integer Public Get, Set Age

    ‘A read-only field + property

    Private mName As String Public Get Name

    ‘A write-only field + property

    Private mDirty As Boolean Public Set Dirty

    Best regards,

    Branco Medeiros

    Reply
  3. Anthony D. Green, MCTS

    I disagree completely, with respect.

    I hated the old syntax and it was one of the larger motivating factors for my move to VB.NET.

    While I understand that VS isn’t neccessarily the editor in use you have to admit that between autocorrect and code snippets and the fact that VS injects the bulk of the declaration for you I wouldn’t consider the amount of typing absurd.

    In fact, I speculate that the decision to use ReadOnly/WriteOnly was motivated possibly by the fact that if you type ‘ReadOnly Propert Name As String’ and hit [Enter] VS can ommit the Set and vice-versa.

    Lastly, I SO agree with you about the shortcut property declaration syntax. After I say that C++/CLI had such a syntax I was uber jealous. Why I sould want to type ‘Get, Set’ when I could reuse ReadOnly and WriteOnly is beyond me. But at the end of the day I think the Code Snippets may be the most flexible option in the end because then you get more control over the baking store of mixed accessor visibility.

    Reply
  4. Pingback: Computer Science Teacher - Thoug

  5. Richard J. Rothery Jr.

    Funny enough I was just going over the rnd function and randomize statement in VB the other day commenting on the fact that they should be updated.

    For those interested random.org has some interesting tidbits concerning pseudo and true random number generation.

    Nice to see others on a global scale delving into this. I will copy the above code and see if it can be of use in my own implementations. I must investigate into the Mersenne Twister algorithm.

    Best Regards,

    Richard J. Rothery Jr.

    Reply
  6. Anthony D. Green, MCTS

    Paul,

    P.S. It really is great to see you eating your own dogfood so-to-speak. I imagined the VB team as a bunch of demented C programmers. It’s nice to see the language developers actually code something rather than just designing, discussing, and advertising (no offense).

    Do you think you’ll ever get VB to the point where it’s compiler is written in VB? Isn’t that like the ultimate programming language Right of Passage?

    Reply
  7. Mark Hutchinson

    I wrote an article on the weaknesses of the (classic) VB PRNG functions:

    http://www.15seconds.com/issue/051110.htm

    Summary: Major weakness is 64K limit in unique seeds being used. Minor weakness is 2^24 period length of the sequences.

    I’m working on a sequel to my first article, indicating several easy (to sophisticated) ways to overcome these weaknesses.

    ============

    Microsoft now states in their help files and online documentation that the VB PRNG functions are weak and should not be used for cryptographic purposes.

    Changing the VB PRNG functions would break applications.

    Reply
  8. Peter

    I am trying to convert this VB version to C#. Every thing seams fine until I ran into to the “Static local” issue. In C#, you can’t declare any variable using “static” key within a method. So referring to the method “GenerateUInt32()” in your VB sample code, Is that ok to declare “mag01()” as class-level static variable?

    I mean like:

    Original in VB:

    Public Function GenerateUInt32() As UInteger

    Static mag01() As UInteger = {&H0UI, MATRIX_A}

    End Function

    In C#:

    private static UInt32[] mag01; //Class-Level

    public UInt32 NextUInt32()

    {

    mag01 = new UInt32[] {0x0, MATRIX_A};

    }

    Reply
  9. Peter

    I am trying to convert this VB version to C#. Every thing seams fine until I ran into to the “Static local” issue. In C#, you can’t declare any variable using “static” key within a method. So referring to the method “GenerateUInt32()” in your VB sample code, Is that ok to declare “mag01()” as class-level static variable?

    I mean like:

    Original in VB:

    Public Function GenerateUInt32() As UInteger

    Static mag01() As UInteger = {&H0UI, MATRIX_A}

    End Function

    In C#:

    private static UInt32[] mag01; //Class-Level

    public UInt32 NextUInt32()

    {

    mag01 = new UInt32[] {0x0, MATRIX_A};

    }

    Reply
  10. Randolph

    I was wondering why the static variable was being used anyway, and found out that replacing it with a class-level defined variable made the algorithm 3 times faster (in VB).

    ‘class level

    Private mag01() As UInteger = {&H0UI, MATRIX_A}

    Reply

Leave a Reply to Peter Cancel reply

Your email address will not be published. Required fields are marked *