http://qs321.pair.com?node_id=195149

mp has asked for the wisdom of the Perl Monks concerning the following question:

For use in a shuffling algorithm, 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.

I currently do:

srand($seed) ... $j = int rand ($n + 1); ...
inside a Fisher-Yates shuffle algorithm. This works, but also "taints" the random number generator by setting the seed to a deterministic value. Since this code runs under mod_perl, it is possible that later code will require a random number that is not so deterministically chosen, so I would like to avoid leaving the seed set to a deterministic value.

Is there a way to find out what the current seed is, so that I can restore it after generating the pseudo random sequence? Would calling srand() with no arguments after the deterministic sequence generation is complete be adequate, with regard to what perldoc -f srand says?

     Do not call "srand" multiple times in your program
     unless you know exactly what you're doing and why
     you're doing it.  The point of the function is to
     "seed" the "rand" function so that "rand" can pro­
     duce a different sequence each time you run your
     program.  Just do it once at the top of your pro­
     gram, or you won't get random numbers out of
     "rand"!

Replies are listed 'Best First'.
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.

      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.
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.";
    
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
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
      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.
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
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

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.