Skip to main content

by Aaron Ballman

A great feature of REALbasic 2006r1 was the introduction of a many new integer data types. You can now use signed and unsigned integers of varying degrees of precision. This opens up a new realm of algorithms that can be implemented easily in REALbasic.

One such class of algorithms are random number generators. Typically, these involve a lot of math (obviously), and the math relies on a lot of integer functionality. For instance, it assumes that overflow behaves a certain way, that math on unsigned integers behaves a certain way, etc. Since REALbasic has introduced all of these new data types, I wanted to chance to test them out. So I decided to implement the Mersenne twister pseudo-random number generation algorithm.

If you're interested in learning more about what the Mersenne twister algorithm is, I suggest checking out the Wiki for the algorithm. It has a good run-down of the concept, with links to even more in-depth information.

However, you're probably interested in the REALbasic implementation itself. The bulk of the algorithm exists in two functions -- the initialization and the 32-bit number generator.

Sub InitByArray(ParamArray init_key as UInt32)
  dim i, j, k as Integer

  dim key_length as Integer = UBound( init_key ) + 1

  init_genrand( 19650218 )

  i = 1
  j = 0
  if N > key_length then k = N else k = key_length

  while k > 0
    mt( i ) = Bitwise.BitXor( mt( i ), (Bitwise.BitXor( mt( i - 1 ), Bitwise.ShiftRight( mt( i - 1 ), 30 ) ) * 1664525) ) + init_key( j ) + j

    ' Again, I don't think this is needed for RB
    'mt( i ) = Bitwise.BitAnd( mt( i ), &hffffffff )

    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

    k = k - 1
  wend

  for k = N - 1 downto 0
    mt( i ) = Bitwise.BitXor( mt( i ), (Bitwise.BitXor( mt( i - 1 ), Bitwise.ShiftRight( mt( i - 1 ), 30 ) ) * 1566083941) ) - i

    ' Again, I don't think this is needed for RB
    'mt( i ) = Bitwise.BitAnd( mt( i ), &hffffffff )

    i = i + 1

    if i >= N then
      mt( 0 ) = mt( N - 1 )
      i = 1
    end if
  next k

  mt( 0 ) = &h80000000 // MSB is 1; assuring non-zero initial array
End Sub

Function RandInt32() As UInt32
  // generates a random number on [0,0xffffffff]-interval

  Dim y as UInt32
  static mag01( 2 ) as UInt32 = Array( UInt32( &h0 ), UInt32( MATRIX_A ) )

  if mti >= N then
    dim kk as Integer

    // If init_genrand hasn't been called yet
    if mti = N + 1 then init_genrand( 5489 )  // Use the default seed

    for kk = 0 to N - M - 1
      y = Bitwise.BitOr( Bitwise.BitAnd( mt( kk ), UPPER_MASK ), Bitwise.BitAnd( mt( kk + 1 ), LOWER_MASK ) )
      mt( kk ) = Bitwise.BitXor( Bitwise.BitXor( mt( kk + M ), Bitwise.ShiftRight( y, 1 ) ), mag01( Bitwise.BitAnd( y, &h1 ) ) )
    next kk

    for kk = kk to N - 1 - 1
      y = Bitwise.BitOr( Bitwise.BitAnd( mt( kk ), UPPER_MASK ), Bitwise.BitAnd( mt( kk + 1 ), LOWER_MASK ) )
      mt( kk ) = Bitwise.BitXor( Bitwise.BitXor( mt( kk + (M - N) ), Bitwise.ShiftRight( y, 1 ) ), mag01( Bitwise.BitAnd( y, &h1 ) ) )
    next kk

    y = Bitwise.BitOr( Bitwise.BitAnd( mt( N - 1 ), UPPER_MASK ), Bitwise.BitAnd( mt( 0 ), LOWER_MASK ) )
    mt( N - 1 ) = Bitwise.BitXOr( Bitwise.BitXor( mt( M - 1 ), Bitwise.ShiftRight( y, 1 ) ), mag01( Bitwise.BitAnd( y, &h1 ) ) )

    mti = 0
  end if

  y = mt( mti )
  mti = mti + 1

  // Tempering
  y = Bitwise.BitXor( y, Bitwise.ShiftRight( y, 11 ) )
  y = Bitwise.BitXor( y, Bitwise.BitAnd( Bitwise.ShiftLeft( y, 7 ), &h9d2c5680 ) )
  y = Bitwise.BitXor( y, Bitwise.BitAnd( Bitwise.ShiftLeft( y, 15 ), &hefc60000 ) )
  y = Bitwise.BitXor( y, Bitwise.ShiftRight( y, 18 ) )

  return y
End Function

Most of the other methods rely on these two to generate the random numbers. I won't (couldn't) go into the math behind the algorithm. I trust in the fact that this is a fairly standard algorithm implemented in many other languages for various uses. I ported my code directly from C code found here. If you spot any bugs in my code, or have any questions, please contact me at aaron@aaronballman.com