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.)
re: Probable Solution | Comment 7 of 11 |
(In reply to Probable Solution by Bob)

The premise is that if, say, .753372 is followed by .3299365, it will always be followed by that number-- the hidden seeds have a one-to-one correspondence with the returned number--you just can't access the hidden seeds, nor ask what number follows another, except for the single current position on the list.
  Posted by Charlie on 2005-02-12 17:56:03

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 (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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