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).

  Submitted by Charlie    
Rating: 3.0000 (3 votes)
Solution: (Hide)
Part 1:

Keep a running track record of the last few results. In the case of Rumor Mill it was the number of people who knew the rumor, which was an integer less than or equal to 50. Use each result as a digit in a number in a base large enough to accommodate the values--in the example case, base 50. Make the number of successive trial results held account for a very large number of possibilities, to (almost) rule out accidental matches. Make this a running tally, so the high-order base-50 (or whatever) digit is lopped off and a new digit is inserted at the end for each new result.

Every so often at a specified interval, store this away for comparison. But at each trial, as the tally changes, compare it to the stored one, also keep track of the number of trials that have elapsed since storing the number.

As the specified interval might be smaller than the length of the repetition cycle, each time the number of trials reaches the interval, so that the tally is stored as the comparison tally, increase the interval by some factor, say 1.7 or 2 (making sure you keep it an integer, however), so that eventually the interval will be large enough to encompass a cycle.

In the case of the Rumor Mill simulation, the variable that held the result was called p2Ct. The code added for tracking was:

Initially setting:
trackLim = 10

Then within the loop, after a new result is found:
tracker = tracker * 50
IF tracker > 390624999999999# THEN
quo = INT(tracker / 39062500000000#)
tracker = tracker - quo * 39062500000000#
' this does a MOD, or remainder function
END IF
tracker = tracker + p2Ct - 1

trackCt = trackCt + 1
IF tracker = trackMatch THEN
PRINT "---"; trackCt; "---": trackCt = 0
END IF

IF trackCt = trackLim THEN
trackMatch = tracker: trackCt = 0
trackLim = INT(trackLim * 1.7)
END IF

Part 2:

As this will require keeping track of large numbers of running tallies, it's best to put them out to a disk file. Instead of the modifications above, re-modify the program to save every tally to the file and check against the saved tally from the number of trials back matching the cycle length found in part 1. Keep count of what trial you are on, and when a match is found, report that number: that's where the numbers start cycling. Make sure the random number generator starts with the same seed it did in the run for part 1.

At the beginning of the program:
OPEN "tracker.bin" FOR BINARY AS #2

Within the loop, after each new result:
tracker = tracker * 50
IF tracker > 390624999999999# THEN
quo = INT(tracker / 39062500000000#)
tracker = tracker - quo * 39062500000000#
END IF
tracker = tracker + p2Ct - 1

trackCt = trackCt + 1

PUT #2, 8 * trackCt, tracker
IF trackCt > 194068 THEN
GET #2, 8 * (trackCt - 194068), trackMatch
END IF

IF tracker = trackMatch THEN
PRINT "---"; trackCt; "---"
END IF

Note that the 194068 above is the cycle length that had been found by implementing part 1.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
There is no solution, only statistically relevant testsFrankM2008-01-19 21:21:25
SolutionNo SubjectKen Haley2005-02-20 05:33:58
VB Program (coded algorithm)Penny2005-02-14 03:16:19
SolutionNo SubjectKen Haley2005-02-12 18:14:27
re: Probable SolutionCharlie2005-02-12 17:56:03
Some ThoughtsPossible solutionTristan2005-02-12 17:48:58
another tryLarry2005-02-12 16:12:12
Probable SolutionEric2005-02-12 15:53:50
re: Am I oversimplifying?Charlie2005-02-11 18:08:54
Maybe this would workLarry2005-02-11 17:30:43
QuestionAm I oversimplifying?SteveH2005-02-11 17:25:14
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