Recipe 6.26. Enhancing the Random Number Generator


Problem

You want to greatly extend the cycle length of Visual Basic's pseudorandom number generator.

Solution

Sample code folder: Chapter 06\RepeatRandom

You can use the RNGCryptoServiceProvider class to generate cryptographically strong random numbers, or you can use the technique presented here to greatly extend the cycle length of the standard pseudorandom number generator and make it easier to use.

Discussion

The BetterRandom class presented here uses the standard Rnd() function and the Randomize() initialization method, but it enhances them in several ways. Contrary to what some people claim, it is possible to initialize the random number generator to a unique but repeatable sequence, but the technique is far from obvious. You have to call the Randomize() method immediately after calling the Rnd() function, but only after passing Rnd() a negative numerical value. So, one advantage of this BetterRandom class is the encapsulation of this technique into something that makes a lot more sense. If you instantiate a BetterRandom object by passing any string to it, each unique string initializes the generator to a unique but repeatable state. If you instantiate a BetterRandom object with no string, the system clock generates a unique sequence for every system tick, which means it is always unique.

The cycle length of the generator is greatly enhanced by maintaining a table of pseudorandom Double numbers in the normalized range 0 to 1. Rolling indexes are used to add table entries together along with the next value returned by Rnd(), and the result is brought back into the range 0 to 1 using the Mod operator. The GetNextdouble() function forms the core of this algorithm, as shown here:

 Public Function GetNextDouble() As Double    ' ----- Return the next pseudorandom number as a Double.    ' ----- Move to the next index positions.    Index1 = (Index1 + 1) Mod TableSize    Index2 = (Index2 + 1) Mod TableSize        ' ----- Update the random numbers at those positions.    RandomTable(Index1) += RandomTable(Index2) + Rnd()    RandomTable(Index1) = RandomTable(Index1) Mod 1.0    ' ----- Return the newest random table value.    Return RandomTable(Index1) End Function 

This table keeps the pseudorandom values well mixed while providing a nice flat distribution of the values with excellent statistical results. When the Rnd() function cycles back around to its starting point, the table will be in a completely different state, which means the cycle length of the values returned from this table will be some off-the-chart astronomical value. It simply won't repeat in the amount of time there is in this universe to exercise the algorithm.

The table size is set to 32, but feel free to make the table larger or smaller as desired. A larger table will be slightly slower to initialize, but subsequent pseudorandom numbers will be calculated and returned just as fast.

Another advantage of this class is that it can be used to return several types of pseudorandom numbers. The GetNexTDouble() function, which is demonstrated in this recipe, returns a double-precision value between 0 and 1. The next few recipes in this chapter will demonstrate how the BetterRandom class can be used to return several other types of pseudorandom numbers. The code for the class is presented here in its entirety for easy review:

 Public Class BetterRandom    Private Const TableSize As Integer = 32    Private RandomTable(TableSize - 1) As Double    Private Index1 As Integer    Private Index2 As Integer    Public Sub New()       ' ----- Generate truly pseudorandom numbers.       InitRandom(Now.Ticks.ToString)    End Sub    Public Sub New(ByVal Key As String)       ' ----- Generate a repeatable random sequence.       InitRandom(Key)    End Sub    Private Sub InitRandom(ByVal repeatKey As String)       ' ----- Prepare the random number generator.       Dim stringIndex As Integer       Dim workNumber As Double       Dim counter As Integer       ' ----- All sequences start with the same base sequence.       Randomize(Rnd(-1))       ' ----- Initialize the table using the key string.       For counter = 0 To TableSize - 1          stringIndex = counter Mod repeatKey.Length          workNumber = Math.PI / _             Asc(repeatKey.Substring(stringIndex, 1))          RandomTable(counter) = (Rnd() + workNumber) Mod 1.0       Next counter       ' ----- Set the starting state for the table.       Index1 = TableSize \ 2       Index2 = TableSize \ 3       ' ----- Cycle through a bunch of values to get a good       '       starting mix.       For counter = 0 To TableSize * 5          GetNextDouble()       Next counter       ' ----- Reset the random sequence based on our       '       preparations.       Randomize(Rnd(-GetNextSingle()))    End Sub    Public Function GetNextDouble() As Double       ' ----- Return the next pseudorandom number as       '       a Double.       ' ----- Move to the next index positions.       Index1 = (Index1 + 1) Mod TableSize       Index2 = (Index2 + 1) Mod TableSize       ' ----- Update the random numbers at those positions.       RandomTable(Index1) += RandomTable(Index2) + Rnd()       RandomTable(Index1) = RandomTable(Index1) Mod 1.0       ' ----- Return the newest random table value.       Return RandomTable(Index1)    End Function    Public Function GetNextSingle() As Single       ' ----- Return the next pseudorandom number as       '       a Single.       Return CSng(GetNextDouble())    End Function    Public Function GetNextInteger(ByVal minInt As Integer, _          ByVal maxInt As Integer) As Integer       ' ----- Return the next pseudorandom number within an       '       Integer range.       Return CInt(Int(GetNextDouble() * _          (maxInt - minInt + 1.0) + minInt))    End Function    Public Function GetNextReal(ByVal minReal As Double, _          ByVal maxReal As Double) As Double       ' ----- Return the next pseudorandom number within a       '       floating-point range.       Return GetNextDouble() * (maxReal - minReal) + minReal    End Function    Public Function GetNextNormal(ByVal mean As Double, _          ByVal stdDev As Double) As Double       ' ----- Return the next pseudorandom number adjusted       '       to a normal distribution curve.       Dim x As Double       Dim y As Double       Dim factor As Double       Dim radiusSquared As Double       Do          x = GetNextReal(-1, 1)          y = GetNextReal(-1, 1)          radiusSquared = x * x + y * y       Loop Until radiusSquared <= 1.0       factor = Math.Sqrt(-2.0 * Math.Log(radiusSquared) / _          radiusSquared)       Return x * factor * stdDev + mean    End Function    Public Function GetNextExp(ByVal mean As Double) As Double       ' ----- Return the next pseudorandom number adjusted       '       for exponential distribution.       Return -Math.Log(GetNextDouble) * mean    End Function End Class 

The following code demonstrates the BetterRandom class by generating two short sequences of pseudorandom Double numbers in the range 0 to 1. The first sequence is generated uniquely each time by not passing a string during initialization of the BetterRandom object. The second sequence uses the same string each time for initialization, and therefore the sequence is always repeated:

 Dim result As New System.Text.StringBuilder Dim generator As BetterRandom result.AppendLine("Never the same sequence:") generator = New BetterRandom result.AppendLine(generator.GetNextDouble.ToString) result.AppendLine(generator.GetNextDouble.ToString) result.AppendLine(generator.GetNextDouble.ToString) result.AppendLine() result.AppendLine("Always the same sequence:") generator = New BetterRandom( _    "Every string creates a unique, repeatable sequence") result.AppendLine(generator.GetNextDouble.ToString) result.AppendLine(generator.GetNextDouble.ToString) result.AppendLine(generator.GetNextDouble.ToString) MsgBox(result.ToString()) 

Figure 6-26 shows the never-and always-repeating sequences generated by this demonstration code.

Figure 6-26. Two pseudorandom sequences are generated: one that's always unique and one that always repeats


See Also

Search Visual Studio Help for "Random Class" and "RNGCryptoServiceProvider Class" for information about other ways to generate pseudorandom numbers in Visual Basic.




Visual Basic 2005 Cookbook(c) Solutions for VB 2005 Programmers
Visual Basic 2005 Cookbook: Solutions for VB 2005 Programmers (Cookbooks (OReilly))
ISBN: 0596101775
EAN: 2147483647
Year: 2006
Pages: 400

Similar book on Amazon

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net