Re: Generating Repeatable Pseudorandom Sequences
by dws (Chancellor) on Sep 04, 2002 at 18:28 UTC
|
For use in a shuffling algorithm, I need to be able to generate repeatable pseudo random sequences ... this code runs under mod_perl, it is possible that later code will require a random number that is not so deterministically chosen
Sounds like you needs to find or implement a random number generator that keeps its state within in instance of a package. That way you can have several generators active without them affecting each other (or interfering with rand() et al.).
A search on search.cpan.org for "random" turns up a number of hits, including one for Math::Random, which looks like it might suit your purposes.
| [reply] [Watch: Dir/Any] |
|
Thank you. After reading your reply, I realized that I really just needed a random number generator that could be seeded and that would not interfere with the builtin rand(). I looked at Math::Random, but ended up settling on Math::Random::MT. I ran some tests of the shuffle algorithm (to check the distribution of the permutations it would produce) with it in place in the Fisher-Yates shuffle algorithm and a set of seeds that were sequential, and it did a good enough job for this application.
| [reply] [Watch: Dir/Any] |
Re: Generating Repeatable Pseudorandom Sequences
by sauoq (Abbot) on Sep 04, 2002 at 18:33 UTC
|
The default behavior for srand (in newer perls) is to try to give you something much less guessable (via /dev/urandom or a combination of the time, process id, and "some other things.")
You don't need to call it (with newer perls) because it is called the first time you call rand().
If you want the same pseudorandom sequence repeatedly, you can get it by repeatedly seeding the generator with the same value. In other words, srand(1); print rand(3) will always print the same value.
-sauoq
"My two cents aren't worth a dime.";
| [reply] [Watch: Dir/Any] [d/l] |
Re: Generating Repeatable Pseudorandom Sequences
by thinker (Parson) on Sep 04, 2002 at 18:34 UTC
|
Hi mp,
All you have to do is call srand() with the same value every time. So use a constant, or even a literal, instead of a variable.
So, if your program begins srand(42), it will always return the same sequence of random numbers.
Hope this helps
thinker | [reply] [Watch: Dir/Any] [d/l] |
Re: Generating Repeatable Pseudorandom Sequences
by waswas-fng (Curate) on Sep 04, 2002 at 19:25 UTC
|
I guess I am missing the point of the question, first you ask:
I need to be able to generate repeatable pseudo random sequences of integers in a range 1-N, such that given the same (integer) seed, the same sequence will always be produced. Then: so I would like to avoid leaving the seed set to a deterministic value.
So it looks like you are asking for 2 exclusive things? rephrased it looks like "I need to be able to reproduce the random number sequence generated" and then "I don’t like being able to reproduce the random number sequence generated". Can you clear up what you are asking here? I guess the bottom line the way the question stands is that you _need_ a known seed to reproduce the random sequence...
Thanks! -Waswas
| [reply] [Watch: Dir/Any] |
|
Sorry if I was unclear. The requirements are not mutually exclusive, I just need different types of "random" numbers at different places in the code. The shuffling subroutine needs to use a deterministic sequence of pseudo random (not truly random) numbers that are repeatable given the same seed. Other code outside the shuffle algorithm may eventually need to use random numbers based on rand() that are not repeatable like those used in the shuffle algorithm. Since this is a rather large persistent (mod_perl) application, it is difficult to foresee where rand() will be used in other code outside the shuffle subroutine, so I would like to avoid "tainting" it with a deterministic seed, or at least clean up afterwards by using a good seed.
What I am writing is a shuffle that can be seeded to always produce exactly one permutation per seed, but that when run with different seeds (seeds that are sequential integers, with some gaps) will produce a set of permutations that are reasonably uniformly distributed. I.e., if I sort the array qw(a b c d) 2400 times using 2400 different seeds, I should expect to see each of the 24 possible permutations about 100 times (plus/minus some tolerance).
Thanks to input from dws above, here is the code I wound up using, which meets my requirements and avoids altering the seed used by rand().
use Math::Random::MT ();
sub shuffle {
my $self = shift;
my $seed = shift;
my $array = $self;
# ||rand() in case no seed passed to shuffle algorithm
my $mt = Math::Random::MT->new( $seed || rand );
my $i;
for($i = @$array; --$i; ) {
my $j = int( $mt->rand($i + 1) );
@$array[$i, $j] = @$array[$j, $i];
}
}
Thank you all for the replies. | [reply] [Watch: Dir/Any] [d/l] |
Re: Generating Repeatable Pseudorandom Sequences
by ichimunki (Priest) on Sep 04, 2002 at 19:02 UTC
|
On 2nd thought:
dws is right, you need to use a module or something, since the approach I list below is probably not thread-safe.
You have the right idea, when you want to generate a sequence reliably, use srand($seed), keeping $seed consistent across calls to srand. Each time you call srand() this resets the random number generator. If you want to "clear" the random number generator for more random usage, just call srand() with no seed.
#!/usr/bin/pseudocode
srand($seed);
print rand, rand, rand -> 1, 2, 3
srand($seed);
print rand, rand, rand -> 1, 2, 3
srand();
print rand, rand, rand -> 42, 256, 3.14
srand($seed);
print rand, rand, rand -> 1, 2, 3
| [reply] [Watch: Dir/Any] [d/l] |
Re: Generating Repeatable Pseudorandom Sequences
by Abigail-II (Bishop) on Sep 05, 2002 at 16:51 UTC
|
Calling srand more than once is not recommended,
but that doesn't mean the results are always bad. It depends a bit
on the needs of the rest of the program, but you might be able
to call srand with a known seed just before you
sort, and after the sort, you call srand without
an argument.
But there's a totally different approach. If you need to shuffle
an array using the same permutation multiple times, instead of playing
games by seeding a PRN generator with the same seed, you could just
shuffle the numbers 0 .. $#array and remember them
(say, in an array @perm_indices). Then, if you need
to shuffle an array again, you do:
@shuffled = @array [@perm_indices];
You may be able to use the Memoize module to this storing for you.
Abigail | [reply] [Watch: Dir/Any] [d/l] [select] |
Re: Generating Repeatable Pseudorandom Sequences
by Anonymous Monk on Sep 05, 2002 at 16:36 UTC
|
For cases when you can't, or don't want to, rely on an external module, this is quick, simple, and good enough for non scientific computing:
sub make_random_generator {
my ($seed, $min, $max) = @_;
# DO NOT CHANGE THESE
my $a = 7 ** 5;
my $m = (2 ** 31) - 1;
# if seed was zero this generator will return zeros
# forever, set it to some arbitrary value
if ($seed == 0) { $seed = 12345678; }
unless (defined $min) { $min = 0; }
unless (defined $max) { $max = $m; }
if ($max < $min) {
my $t = $min;
$min = $max;
$max = $t;
}
return sub {
$seed = ($a * $seed) % $m;
# "scale" $seed to the range ($min,$max)
return int ((($seed / $m) * ($max - $min)) + $min);
}
}
use it like this:
for my $seq_n (1..10) {
print "random sequence with seed $seq_n:\n";
my $gen = make_random_generator(rand, 0, 1000);
print join ", ", map { $gen->() } 1 .. 10;
print "\n";
}
this will return the same 10 pseudo random sequences every time you run it. | [reply] [Watch: Dir/Any] |