All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Random Check (Posted on 2005-02-11) Difficulty: 3 of 5
In doing computer simulations, such as the one I wrote for simulating the results of part 2 of Rumor Mill, one often uses a random number generator that's built into the computer language. These generators are based on a seed (some arbitrary number) and are mixed up at each step that calls for a random number. There are only a finite number of seeds, and each one is based mechanically on the previous, so they necessarily repeat after a while.

The seed is kept internally, away from the programmer's view, so the programmer can't ask for, say, the next random number after .753372.

If one suspects that the repetition cycle is actually occuring within the length of the run that he needs, what algorithm can you put into the program to find the period with which your results are repeating (and are therefore no longer random, or rather no longer independent trials)? Assume you do not have room to store all the numbers as they arrive, nor can you afford the time it would take to compare each new number to all the preceding numbers.

Then also, how do you determine where the repetition cycle begins (after what iteration of the loop of trials).

See The Solution Submitted by Charlie    
Rating: 3.0000 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution No Subject | Comment 10 of 11 |

The following is a VB.Net program that implements the algorithm described in my previous post.

Explanation:  PhonyRandom is a terrible random number generator--it doesn't even try to generate anything random, but it has the necessary characteristics to use as a surrogate for a real random number generator for purposes of this test.  PhonyRandom will return the following sequence of integers: 246, 245, 244, 243, 242, 241, 240, 239, 238, 237, 236... 3, 2, 1, 237, 236, 235, etc.  Thus this generator has a period of 237, and begins repeating at position 10 (where we see the first 237).

The Main program knows nothing about this.  Its mission is to determine the period and first point where the sequence begins to repeat.  Running this program produces the following output in a console window:

Period is 237
Repetition starts at position 10

...which is exactly what we were looking for.  If you change the class to use a period greater than 1000, the output will be

period is more than 1000

...which is also what we'd expect.

_________________________________________

Option Strict On
Module Module1
    Class PhonyRandom

        Dim m_number As Integer

        Public Sub New()
            m_number = 247
        End Sub

        Public Function NextNo() As Integer
            Dim period As Integer = 237
            m_number -= 1
            If m_number < 1 Then m_number = period
            Return m_number
        End Function

    End Class

    Sub Main()
        Dim maxTrials As Integer = 1000
        Dim r As New PhonyRandom
        ' Assume the test will need maxTrials random numbers...
        Dim i As Integer
        For i = 1 To maxTrials
            r.NextNo() 'gets a random and discards it.
        Next
        Dim CompareTo As Integer = r.NextNo
        For i = 1 To maxTrials
            If r.NextNo = CompareTo Then
                Exit For
            End If
        Next
        If i < maxTrials Then
            Dim period As Integer = i
            Console.WriteLine("Period is {0}", period)
            r = New PhonyRandom
            Dim r2 As New PhonyRandom
            For i = 1 To period
                r.NextNo()
            Next
            i = 0
            Dim x, y As Integer
            Do
                i += 1
                x = r.NextNo
                y = r2.NextNo
            Loop Until x = y
            Console.WriteLine("Repetition starts at position {0}", i)
        Else
            Console.WriteLine("period is more than {0}", maxTrials)
        End If
        Console.ReadLine()
    End Sub
End Module

_________________________________________

  Posted by Ken Haley on 2005-02-20 05:33:58
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information