mardi 20 août 2019

How to generate a good seed

I'm looking for a method to generate a good seed for generating different series of random numbers in processes that starts at the same time. I would like to avoid using one of the math or crypto libraries because I'm picking random numbers very frequently and my cpu resources are very limited.

I found few example for setting seeds. I tested them using the following method:

  1. short program that picks 100 random numbers out of 5000 options. So each value has 2% chance to be selected.
  2. run this program 100 times, so in theory, in a truly random environment, all possible values should be picked at least once.
  3. count the number of values that were not selected at all.

This is the perl code I used. In each test I opt in only one method for generating seed:

#!/usr/bin/perl
#$seed=5432;
#$seed=(time ^ $$);
#$seed=($$ ^ unpack "%L*", `ps axww | gzip -f`);
$seed=(time ^ $$ ^ unpack "%L*", `ps axww | gzip -f`);

srand ($seed);

for ($i=0 ; $i< 100; $i++) {
        printf ("%03d \n", rand (5000)+1000);
}


I ran the program 100 time and counted the values NOT selected using:

# run the program 100 times
for i in `seq 0 99`; do /tmp/rand_test.pl ; done  > /tmp/list.txt
# test 1000 values (out of 5000). It should be good-enough representation.
for i in `seq 1000 1999`; do echo -n "$i  "; grep -c $i /tmp/list.txt; done   | grep " 0" | wc -l


The table shows the result of the tests (Lower value is better):

count      Seed generation method
114    default - the line: "srand ($seed);" is commented ou
986    constant seed (5432)
122    time ^ $$
125    $$ ^ unpack "%L*", `ps axww | gzip -f`
163    time ^ $$ ^ unpack "%L*", `ps axww | gzip -f`

The constant seed method showed 986 or 1000 values not selected. In other words, only 1.4% of the possible values were selected. This is close enough to the 2% that was expected.

However, I expected that the last option that was recommended in few places, would be significantly better than the default.

Is there any better method to generate a seed for each of the processes?




Aucun commentaire:

Enregistrer un commentaire