Re: bad default srand seed?

At 5:09 AM -0700 2/9/00, Tom Christiansen wrote:
>Witness:
>
>% repeat 20 perl -le '@n = sort { rand() <=> rand() } 1 .. 20; print "@n"'
>17 5 4 7 1 14 12 3 11 9 20 13 8 6 16 19 15 18 2 10
>17 5 4 7 1 14 12 3 11 9 20 13 8 6 16 19 15 18 2 10
>2 18 4 17 3 9 1 12 10 14 8 6 19 13 16 11 7 15 5 20
>2 18 4 17 3 9 1 12 10 14 8 6 19 13 16 11 7 15 5 20
>17 13 1 6 5 4 9 7 16 20 10 12 18 15 8 11 3 19 14 2
>14 9 5 17 8 7 16 10 1 18 13 12 6 15 4 2 19 3 11 20
>2 18 5 6 9 3 4 10 1 14 20 11 13 15 19 17 8 16 7 12
>17 18 14 7 19 16 15 12 10 11 2 3 6 5 9 4 13 8 1 20
>14 1 3 7 13 8 6 19 5 9 10 12 4 20 11 15 16 2 18 17
>6 10 7 15 4 17 3 16 13 9 12 19 1 2 5 8 14 11 18 20
>11 18 3 8 4 15 2 19 10 12 16 9 6 7 13 17 14 1 5 20
>3 7 17 19 4 14 15 11 12 6 10 9 2 8 16 18 1 13 5 20
>3 7 17 19 4 14 15 11 12 6 10 9 2 8 16 18 1 13 5 20
>18 1 6 9 13 5 12 10 20 17 19 11 15 7 14 16 3 8 4 2
>18 1 6 9 13 5 12 10 20 17 19 11 15 7 14 16 3 8 4 2
>5 19 6 20 7 1 3 12 11 18 2 9 4 14 10 16 15 17 13 8
>11 19 1 2 16 17 6 13 9 8 3 12 5 14 20 4 15 7 10 18
>1 20 15 13 4 6 7 8 19 10 5 16 2 9 11 12 18 17 14 3
>10 13 1 19 4 20 5 11 18 7 3 8 12 15 14 2 17 6 16 9
>11 17 18 3 5 6 9 20 12 2 16 4 13 14 8 10 15 1 7 19

linux% repeat 20 perl -le '@n = sort { rand() <=> rand() } 1 .. 20; print "@n"'
17 8 1 7 15 4 18 6 5 12 9 11 14 13 16 19 2 10 3 20
12 5 4 3 16 1 18 10 6 17 15 11 8 13 2 19 7 14 9 20
3 18 1 4 6 5 11 17 2 16 10 13 19 9 7 15 14 12 8 20
12 4 8 13 20 3 9 7 10 19 14 1 16 2 6 17 18 15 5 11
1 14 10 8 5 18 2 16 9 20 3 19 12 15 6 17 13 7 4 11
4 16 14 5 18 17 20 9 10 12 19 6 11 7 15 3 13 1 2 8
3 13 19 17 5 18 4 7 9 11 15 12 2 16 6 10 14 8 1 20
17 16 19 1 6 12 8 9 18 20 4 11 13 14 3 15 2 10 5 7
13 3 8 14 9 5 10 6 18 11 1 15 2 20 17 7 16 19 12 4
2 3 16 14 11 15 12 7 5 10 8 13 18 6 20 4 9 19 1 17
19 3 7 13 9 5 15 6 10 8 1 11 12 20 4 14 17 2 18 16
9 18 15 19 4 1 3 17 6 7 10 13 12 11 5 8 16 20 2 14
2 10 7 5 6 12 3 17 19 18 11 13 9 4 8 16 14 15 20 1
9 20 5 14 4 12 13 3 7 18 11 15 10 17 8 6 1 16 19 2
6 12 10 16 5 15 2 1 8 11 17 3 13 9 4 18 14 7 19 20
7 9 18 3 12 17 14 6 5 4 2 8 19 10 1 16 13 11 15 20
18 15 1 16 3 4 9 13 19 5 10 6 14 11 7 2 12 17 8 20
11 2 18 13 14 7 12 17 8 3 10 5 4 1 9 16 15 6 20 19
6 2 16 7 14 12 15 9 3 19 20 11 17 10 1 5 4 13 18 8
18 2 11 14 12 6 5 8 15 13 16 9 19 20 1 10 17 3 7 4

linux% perl -v

This is perl, v5.5.650 built for ppc-linux

MacPerl (5.004) gives:

10 8 19 4 3 2 18 11 16 1 9 13 12 20 5 6 17 15 14 7
9 17 6 8 5 13 18 1 20 12 2 4 10 14 11 3 15 7 19 16
6 2 20 17 9 16 8 5 19 12 1 11 7 14 15 4 10 13 3 18
2 8 19 10 15 14 1 13 16 18 12 11 4 17 6 5 7 3 9 20
16 13 3 9 7 14 17 2 10 1 8 4 15 12 11 5 18 20 19 6
6 2 3 12 20 18 15 4 10 1 11 14 7 5 13 9 8 17 16 19
1 14 17 5 10 6 12 15 11 19 16 8 7 18 2 3 20 13 9 4
8 5 10 18 14 17 15 3 19 16 11 9 20 1 7 12 13 4 6 2
13 14 12 5 8 9 15 1 6 16 20 3 19 10 2 17 4 18 11 7
13 12 10 11 3 2 14 5 6 19 20 18 8 17 7 9 16 15 4 1
13 2 8 20 12 7 5 15 11 9 14 10 6 1 16 3 19 17 4 18
15 19 5 20 14 10 12 6 1 11 9 2 7 8 16 17 3 4 13 18
6 20 18 11 16 13 7 5 14 3 10 17 12 4 19 1 9 15 8 2
6 20 5 15 10 14 19 1 12 8 4 3 11 16 13 17 7 18 2 9
8 4 1 20 18 15 19 9 13 3 2 6 14 7 12 16 17 10 11 5
15 13 8 9 17 16 1 3 11 19 20 2 5 14 4 18 12 6 7 10
17 10 5 2 19 13 14 4 3 9 20 18 11 8 12 6 16 1 7 15
13 2 14 1 20 16 18 9 6 11 4 8 10 12 7 17 19 3 15 5
9 16 3 14 13 11 1 15 6 8 12 17 10 5 18 20 7 2 4 19
20 15 11 8 5 6 14 3 19 7 12 18 16 4 2 9 10 17 1 13

I don't see anything horrible here.  My own favorite way of 
eyeballing random number generators is to produce them a pair at a 
time and plot them, looking for obvious "unrandomness".  (The right 
way is to run it through one of the test suites.)


>Now, that isn't particularly random.  Hm....
>
>% repeat 20 perl -le 'srand; @n = sort { rand() <=> rand() } 1 .. 
>20; print "@n"'
>15 14 18 1 3 6 11 4 13 12 17 10 5 9 20 7 16 8 19 2
>17 20 19 5 9 13 8 4 16 3 18 11 10 7 15 1 12 2 14 6
>16 1 2 9 7 20 6 12 3 13 8 10 14 15 19 11 18 17 5 4
>13 1 3 15 9 6 17 14 4 20 10 18 16 12 7 19 11 2 5 8
>13 1 16 18 5 4 15 17 8 9 10 12 14 19 7 3 2 11 6 20
>13 1 16 18 5 4 15 17 8 9 10 12 14 19 7 3 2 11 6 20
>2 18 4 11 14 5 15 3 16 7 6 1 10 17 12 13 19 8 9 20
>2 18 4 11 14 5 15 3 16 7 6 1 10 17 12 13 19 8 9 20
>2 1 4 9 19 18 3 14 17 16 10 20 5 13 7 8 15 6 11 12
>7 12 3 19 11 13 10 18 4 15 8 17 14 16 5 9 20 2 1 6
>7 12 19 11 15 14 9 8 2 4 20 10 16 6 18 1 5 13 3 17
>17 7 11 4 2 19 3 10 1 6 18 8 15 20 13 9 5 16 12 14
>7 2 13 8 11 16 4 17 1 9 19 12 20 18 15 5 10 6 3 14
>2 18 14 11 8 19 12 3 1 16 6 10 5 20 15 4 7 17 13 9
>6 18 1 2 3 7 9 12 5 15 19 17 10 11 4 14 20 8 16 13
>5 1 3 4 20 2 17 18 11 7 10 14 13 8 6 16 12 9 15 19
>5 1 3 4 20 2 17 18 11 7 10 14 13 8 6 16 12 9 15 19
>10 2 12 16 7 19 20 5 18 14 11 1 9 3 8 17 6 13 15 4
>10 2 12 16 7 19 20 5 18 14 11 1 9 3 8 17 6 13 15 4
>12 11 3 17 20 8 6 18 2 13 5 19 10 7 1 9 14 16 15 4

linux% repeat 20 perl -le 'srand; @n = sort { rand() <=> rand() } 1 
.. 20; print
  "@n"'
5 2 15 8 14 7 18 1 11 4 19 20 9 3 17 13 10 6 12 16
13 18 20 11 19 6 12 8 10 1 2 15 17 4 5 9 16 14 3 7
4 20 11 5 19 17 14 13 9 12 3 6 18 16 15 7 10 1 8 2
16 12 4 2 1 8 13 9 20 10 3 14 19 15 5 6 18 17 11 7
19 4 18 9 14 5 12 8 2 16 20 11 10 13 17 3 6 1 15 7
10 7 20 3 6 1 14 18 11 9 5 15 13 2 12 17 8 16 4 19
16 1 20 14 3 19 8 4 5 18 15 9 10 7 13 2 17 12 11 6
6 15 10 3 2 12 19 7 14 17 18 9 1 13 11 4 5 16 20 8
20 13 15 5 4 17 1 16 9 19 7 10 14 11 8 3 2 12 18 6
20 14 18 4 5 6 17 16 13 15 9 2 19 11 8 1 10 7 3 12
19 16 14 6 11 13 4 7 12 9 18 2 10 20 5 17 8 15 1 3
7 1 11 4 5 13 12 3 17 10 16 2 18 20 14 6 19 8 15 9
3 8 20 6 16 11 7 10 15 19 9 5 13 17 14 18 1 2 4 12
13 14 12 5 4 1 2 10 18 17 11 6 7 20 16 15 3 9 19 8
5 17 10 4 20 1 19 2 9 11 3 15 8 14 16 12 13 18 6 7
18 12 16 4 8 17 10 14 13 19 11 3 20 5 2 1 15 9 7 6
3 4 14 5 19 7 18 17 11 10 13 2 12 16 6 1 15 20 8 9
10 14 8 4 3 18 13 20 1 9 6 7 15 11 16 2 17 12 5 19
6 14 1 3 4 20 11 10 7 18 19 15 8 5 9 12 2 17 16 13
19 16 10 12 1 14 20 4 3 6 7 15 2 11 5 18 9 17 8 13


>
>Oh, curses, is there something wrong with the default srand?
>
>That's with 5.005_54 on OpenBSD.  Running with v5.5.650 produces
>no better results then did 54.  I smell a bad seed.  Seeding it
>myself is *much* better.
>
>% repeat 20 perl -le 'srand(time() ^ ($$ + ($$ << 15))); @n = sort { 
>rand() <=> rand() } 1 .. 20; print "@n"'
>19 16 4 20 12 13 10 2 17 9 1 18 3 14 15 6 7 5 8 11
>6 18 7 19 20 10 5 9 3 8 14 12 13 15 11 16 17 4 1 2
>9 18 15 1 3 5 16 8 19 20 11 4 12 7 10 13 2 17 6 14
>2 20 17 19 3 5 7 4 8 9 14 10 18 13 11 15 1 16 6 12
>1 12 17 4 15 18 20 13 5 9 7 19 10 6 3 14 16 2 8 11
>5 2 11 8 16 19 17 10 9 6 3 4 13 15 12 7 14 1 18 20
>19 6 7 18 2 12 14 10 3 9 4 17 16 20 8 15 11 13 1 5
>1 9 17 16 18 2 15 7 12 11 4 3 5 10 14 13 6 8 19 20
>6 15 3 20 11 2 19 13 12 9 8 10 18 5 16 7 17 14 1 4
>3 2 11 14 15 18 13 12 16 4 17 20 8 9 10 1 7 5 6 19
>7 2 19 14 9 12 8 20 6 10 4 18 13 5 1 3 15 11 16 17
>2 6 1 9 5 7 14 17 18 16 20 10 8 12 15 4 3 11 19 13
>1 11 17 4 13 12 16 7 8 18 2 20 10 19 14 15 6 9 3 5
>6 12 5 11 8 10 2 1 18 19 16 14 13 20 7 4 3 9 15 17
>14 11 17 5 2 20 15 18 1 19 10 3 16 4 7 12 6 8 13 9
>13 6 16 10 12 2 17 20 8 7 1 4 18 11 9 15 3 19 5 14
>13 9 8 19 20 11 18 5 16 7 3 2 17 6 15 14 1 12 10 4
>8 18 12 5 11 17 1 10 3 9 2 16 6 13 14 7 15 20 4 19
>2 3 9 17 18 13 8 1 19 14 12 10 4 11 7 20 16 15 6 5
>11 7 17 14 4 12 8 18 10 20 19 16 3 15 5 1 13 2 9 6
>
>If I don't seed it, every run of 20 produces at least
>one pair of adjacent duplicated lines.
>
>
>% repeat 100 perl -le 'srand; @n = sort { rand() <=> rand() } 1 .. 
>20; print "@n"' | uniq | wc -l

100 every time:

linux% repeat 100 perl -le 'srand; @n = sort { rand() <=> rand() } 1 
.. 20; prin
t "@n"' | uniq | wc -l
     100

even without the srand:

linux% repeat 100 perl -le '@n = sort { rand() <=> rand() } 1 .. 20; 
print "@n"'
  | uniq | wc -l 

     100

Same on Solaris 7 on an Ultra 5 with 5.005_03.  100 every time I tried.

>
>If I use a proper seed, like srand(time() ^ ($$ + ($$ << 15))),
>then I never *once* get any answer but 100 above.  Or run with 20
>repeats, any answer but 20.  And it doesn't matter whether my
>sequence of numbers if 10, 20, 100, or 1000 -- there are still
>around 20% dups, give or take a few.
>
>And yes, I've tested this on the latest and greatest.
>
>This seems to say that the goal of not having to call srand
>has not yet been met.
>
>Ideas?

Now the question is how the seed is chosen, and why it's not working 
on your machines, but is on mine.  You're using Intel, right?  That's 
the obvious difference (PPC and SPARC, both big endian), but I don't 
know why that would matter.

>
>--tom

--
Paul Schinder
schinder@pobox.com

• bad default srand seed? by Tom Christiansen
• Re: bad default srand seed? by simon
• Re: bad default srand seed? by Paul Schinder