ProblemYou want to greatly extend the cycle length of Visual Basic's pseudorandom number generator. SolutionSample 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. DiscussionThe 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 repeatsSee AlsoSearch Visual Studio Help for "Random Class" and "RNGCryptoServiceProvider Class" for information about other ways to generate pseudorandom numbers in Visual Basic. |