srand and rand on NTPerl 5.001-1L-091 
Author Message
 srand and rand on NTPerl 5.001-1L-091

This message originally posted on comp.lang.perl, which I later
found out is dead.  Sigh.

------

So here I am learning Perl, thanks to everybody's friend Randal,
and I'm messing with the code exercises as I work my way through
the book, and I go to do Exercise 3.3, as follows:

"Write a program that reads a list of strings and then selects
and prints a random string from the list."

It goes on to explain the concepts of rand() and srand.  No
problem, I say, that's trivial.  Skipping some of the tricky
overhead that allows perl scripts to self-execute under an NT
command prompt, the core code is:



No problem, right?  Except that, being the suspicious hacker
that I am, I ran it several times in succession, just to test
whether it was really as random as it claimed.  SURPRISE!  It
wasn't.  Hmmmm, I said, I wonder why.  Let's test the random
number generator, taking the definition from the Perl5 manual
that srand is actually srand(time):

srand;
print(time,"\t",rand(6),"\n");

I chose 6 here simply as a fixed upper bound, to make a
search for "non-randomness" more obvious.  Running that a few
times at a prompt, I got a very odd effect, which becomes clear
in the output of a version that repeats those two lines, waiting
for a carriage return in between to allow time to pass.  Take a
look:

while(<STDIN>){
  srand;
  print (time,"\t",rand(6));

Quote:
}

produces:

822096380       0.767578125
822096382       0.76885986328125
822096384       0.7701416015625
822096385       0.77069091796875
822096387       0.77178955078125
...

You get the idea.  Once that gets chopped, it's still 0 for the
random output, and it looks like it would take quite a while to
change to being 1 or 2 or whatever.  So imagine that you've
written a perl script that allows you to change the order in
which ftp mirror sites appear on an HTML page, to do a rough
form of load-balancing (you could even do http redirects this
way, and have a front-end server that load-balances across
multiple http servers).  The HTML page would be the same for
quite a while before it changed!  Not terribly balanced . . . .
In any case, the problem seems to be that the low order bits of
the time are virtually insignificant to the seeding function
srand, which seems awfully wrong to me . . . but then I'm always
suspicious of pseudo-random number generators after spending a
lot of time with Knuth.  :-)

So, the big question: is this a Perl bug, a Perl5 bug, or an NT
porting bug?

-'f



Mon, 13 Jul 1998 03:00:00 GMT  
 srand and rand on NTPerl 5.001-1L-091

Quote:

> times at a prompt, I got a very odd effect, which becomes clear
> in the output of a version that repeats those two lines, waiting
> for a carriage return in between to allow time to pass.  Take a
> look:

> while(<STDIN>){
>   srand;
>   print (time,"\t",rand(6));
> }

Did you sit on the return key to get your results? Try this:

srand;                  # <-- Seed once.
while(<STDIN>){
   print (time,"\t",rand(6));

Quote:
}

There is little point in seeding every loop, that won't give you
such random numbers.

Quote:
> So, the big question: is this a Perl bug, a Perl5 bug, or an NT
> porting bug?

I guess you are not seeding correctly, at least in the above example.

--
Dave Pearson              | Let us not assasinate this lad further, Senator.

Bass Player for the       |   Have you no sense of decency, Sir?
Cheri-Woodpeckers         |    At long last, have you no sense of decency?



Tue, 14 Jul 1998 03:00:00 GMT  
 srand and rand on NTPerl 5.001-1L-091

Quote:

>> while(<STDIN>){
>>   srand;
>>   print (time,"\t",rand(6));
>> }
>Did you sit on the return key to get your results? Try this:
> srand;                  # <-- Seed once.
> while(<STDIN>){
>    print (time,"\t",rand(6));
> }
>There is little point in seeding every loop,that won't give you
>such random numbers.

*SIGH*.  You know, I get this every time I post a basic question
on the Internet.  I assume one of three causes:

1)  I worded it very badly.
2)  After a decade and a half of programming, I'm still a total
    idiot, and never bothered to think about what I was saying.
3)  This is a natural response when you challenge a basic
    assumption.

Somehow, I'm guessing it's good ol' #3.  Allow me to vent a
little frustration at this point:

SELF_RIGHTEOUSNESS++;
print "YES, I KNOW THAT, FOR HEAVEN'S SAKE!\n";
SELF_RIGHTEOUSNESS--;

Ahhh, much better.  My point was that any halfway rational
seeding function should give wildly different seeds, even for
two seeds numerically close together, otherwise you get a
failure case like the one I described -- that if a fresh script
is launched every time a (fairly common) event happens, each
script should be able to expect reasonably random numbers from
the getgo; but with an srand() like this one, unless you add
some ridiculous overhead to remember the last random value from
a previous invocation of the program, every invocation of that
script for a non-trivial length of time will see the random
number sequence starting with the same value.

Hmmm.  Rereading the last paragraph, perhaps #1 above was the
real reason for the silly response.  Here, let me explain it
like this:  A reasonable seeding function for a PRNG should
ideally have {srand($seed);rand($limit);} as unrelated to
{srand($seed+1);rand($limit);} as possible, and for NTperl5's
generator, this is not the case.  In fact, with very high
probability, for small $limit values, the two are identical!

Almost makes me want to right a one-way hash to seed the damn
generator with.  Oh well.  In any case, does anybody with Unix
perl know if this is the standard functionality, or if this is a
problem with the NTperl5 version/port?

Or should I just go out and port something from "Applied
Cryptography" to Perl?  :-)

-'f



Wed, 15 Jul 1998 03:00:00 GMT  
 srand and rand on NTPerl 5.001-1L-091

Quote:
>while(<STDIN>){
>  srand;
>  print (time,"\t",rand(6));
>}

User error. srand() should be invoked ONCE at initialization time to seed the
random number generator. Then, call rand() as often as you like, as follows:

  srand();

  foreach $i ( 0..9 ) { $freq[$i] = 0 ; }

  foreach $i ( 1..10000 )
    {
      srand();
      $R = int( rand(10) ) ; # random integer 0-9
      $freq[$R] ++         ; # increment frequency count
    }

  foreach $i ( 0..9 )
    {
      print ( $i , "\t", $freq[$i] ) ;
    }

N.

--
The opinions expressed in this message are my own personal views
and do not reflect the official views of Microsoft Corporation.



Wed, 15 Jul 1998 03:00:00 GMT  
 srand and rand on NTPerl 5.001-1L-091

Quote:

> *SIGH*.  You know, I get this every time I post a basic question
> on the Internet.  I assume one of three causes:

> 1)  I worded it very badly.
> 2)  After a decade and a half of programming, I'm still a total
>     idiot, and never bothered to think about what I was saying.
> 3)  This is a natural response when you challenge a basic
>     assumption.

> Somehow, I'm guessing it's good ol' #3.  Allow me to vent a
> little frustration at this point:

Hey, well, I don't know you, so I can't suggest #2, but I would, after
reading your reply, strongly suggest that it was #1. Jeez, some people!

Look, srand() is srand(). I'm not saying that is good or bad but srand()
does what srand() does, at least in every language I've used that has had
that concept. Hell, but what do I know, I'm no rocket scientist!

Yeah, you may well be challenging a basic assumption, but it's a well
documented "basic assumption", you got the response your question begged
for, I'm real sorry you didn't get the response you feel you deserved.

Quote:
> Hmmm.  Rereading the last paragraph, perhaps #1 above was the
> real reason for the silly response.  

Well hey, you just might be right there.

I'm ever so sorry I could not provide you with the quality of help you
feel you deserve.

--
Dave Pearson              | Let us not assasinate this lad further, Senator.

Bass Player for the       |   Have you no sense of decency, Sir?
Cheri-Woodpeckers         |    At long last, have you no sense of decency?



Thu, 16 Jul 1998 03:00:00 GMT  
 srand and rand on NTPerl 5.001-1L-091

Quote:

>Jeez, some people!

Hmmmm.  *blinkblink*.

Let me try again, from scratch:

Hi, my name is Geoff Broadwell.  I'm trying to figure out where
to address a major problem, and I'd even be willing to post the
solution if need be.  I would like to know if the irrational
behavior of srand() is a result of the way srand() and rand()
are done in perl, in perl5, or in NTperl5 (in order of
increasing specificity).

Quote:
> Look, srand() is srand(). I'm not saying that is good or bad but srand()
> does what srand() does, at least in every language I've used that has had
> that concept.

But it doesn't!  I'm guessing that perhaps it's because of the
way that perl turns integer seeds into floating point results,
but on all systems I've ever used, however they do it, they
don't get that behavior.  Then again, I've never done random
numbers in Unix (because, honestly, I never had a reason to. :-)

Quote:
> Hell, but what do I know, I'm no rocket scientist!

Look, I'm sorry if this all came off as combative--I was just
expressing my frustration, because I posted a question that
could be interpreted as either an "idiot check" or as a basic
question about the language concepts, and the ONLY response I
got after a week was that I was an idiot.  Not exactly my idea
of fun.

Quote:
> Yeah, you may well be challenging a basic assumption, but it's
> a well
> documented "basic assumption",

Fair enough.  Since I saw no such documentation in either Llama
or Camel, I asked whether it was part of the perl
implementations or something more basic.  You seem to be
suggesting the latter.  Pointers?

Quote:
> you got the response your question begged
> for, I'm real sorry you didn't get the response you feel you
> deserved.

I don't think I deserve anything more than that until anybody
out here in the matrix knows me, I can't be assumed to be an
idiot.  And I think *everybody* deserves that.  It's just a bit
frustrating that a lot of folks out on the net today seem to
have a "guilty until proven innocent" attitude vis-a-vis common
sense, or lack thereof.

Quote:
>> Hmmm.  Rereading the last paragraph, perhaps #1 above was the
>> real reason for the silly response.
> Well hey, you just might be right there.

I never claimed to be a computing god or on speaking terms with
the Muses, just not an idiot.

Quote:
> I'm ever so sorry I could not provide you with the quality of
> help you
> feel you deserve.

I don't have any desire to make enemies.  I'm sorry if I have.  
But allow me to make a suggestion; when you are faced with a
question that has multiple interpretations, answer them all!  
It's good mental exercise, you'll be doing the typing anyway, it
defuses all sorts of flame wars, and maybe it'll teach the
person you're addressing to be more precise.  If you want to
answer questions, and you feel you're qualified (and you
probably are at that), take the roll of teacher.  Guide the
students, don't squelch them.  And never, but never, assume that
an unexpected question was the result of lack of understanding,
even if 99% of them are.

I had a professor in college by the name of William Kahan.  Some
of you may recognize the name; he designed the floating point
logic for HP calculators and 80x87 processors.  He used to say
that everybody was wrong at some time, even *him*.  He felt that
the highest duty of the student was to challenge the assumptions
of his teachers, and the highest duty of the teacher was to take
such challenges seriously, and address them.

All right, you're the teacher in this instance, and I'm the
student.  I've just said that I think perl's implementation of
srand() and rand() are poor.  Now, do you look for the problem,
do you leave it to the student as an exercise to find the
solution, or do you take offense and squelch him?  What would
you do with a classroom full of impressionable young minds?

Oh, and a little late-breaking news . . . the Linux version
works correctly.  :-)  Thanks to--oh damn, I lost the
letter--Peter Rye, I think, for that info.

-'f



Fri, 17 Jul 1998 03:00:00 GMT  
 srand and rand on NTPerl 5.001-1L-091

    [SNIP]

Quote:
>Ahhh, much better.  My point was that any halfway rational
>seeding function should give wildly different seeds, even for
>two seeds numerically close together, otherwise you get a
>failure case like the one I described -- that if a fresh script
>is launched every time a (fairly common) event happens, each
>script should be able to expect reasonably random numbers from
>the getgo; but with an srand() like this one, unless you add
>some ridiculous overhead to remember the last random value from
>a previous invocation of the program, every invocation of that
>script for a non-trivial length of time will see the random
>number sequence starting with the same value.
>Hmmm.  Rereading the last paragraph, perhaps #1 above was the
>real reason for the silly response.  Here, let me explain it
>like this:  A reasonable seeding function for a PRNG should
>ideally have {srand($seed);rand($limit);} as unrelated to
>{srand($seed+1);rand($limit);} as possible, and for NTperl5's
>generator, this is not the case.  In fact, with very high
>probability, for small $limit values, the two are identical!
>Almost makes me want to right a one-way hash to seed the damn
>generator with.  Oh well.  In any case, does anybody with Unix
>perl know if this is the standard functionality, or if this is a
>problem with the NTperl5 version/port?

Err...it's actually a problem with library functions rand() and srand()
underlying PERL's rand() and srand() functions.

Perl for Win32 aka NTPerl call the MS-C runtime library functions which
are (A) 16-bit and (B) not very good in the sense it won't
pass any of the usual statistical tests for randomness, and
(C) I don't believe that the MS-C rand() is a full period generator. Also,
having examinined the source code for the MS-C runtime library rand()/srand()
functions, the first call to rand() is almost certainly warranted to yield a
bogus result because the initial seed [ strand(time()) ] almost certainly lies
outside the period of the generator. A better seed would be [ srand((time() %
32767)+1) ].

A very good (and portable!) PNRG is described in

  "Random Number Generators: Good Ones Are Hard To Find",
  Steve Parks and Keith Miller,
  _Communications_of_the_ACM_, October, 1988

I implemented it in Perl (the PM file) and a validation script
is attached following the end of this message. The .PM file
could probably stand to be tidied a bit, but such is life.

Quote:
>Or should I just go out and port something from "Applied
>Cryptography" to Perl?  :-)

If you want a better seed, you probably should look at a good cryptography
text -- because srand(time()) is about as good as it gets in most libraries.
Parks and Miller in the above-mentioned article suggest that (A) a good seed
function should prompt the user for a seed and that (B) a good seed might be
your social security number.

Hope this helps, [The perls for the Parks and Miller PNRG follow the .sig ]

N.
=======================================================================
Mandatory Disclaimer: The opinions expressed in this message are my own
personal views and do not reflect the official views of Microsoft Corp.
=======================================================================

Here's the perls for the PNRG:

=== RAND.PM begins ===
#!/usr/bin/perl.exe
# == random.pm ======================================================= #
#                                                                      #
# This perl implements the random number generator described in        #
#                                                                      #
#   "Random Number Generators: Good Ones Are Hard To Find",            #
#   Steve Parks and Keith Miller,                                      #
#   _Communications_of_the_ACM_, October, 1988                         #
#                                                                      #
# The core generator has the following properties:                     #
#                                                                      #
#   * The period is 2^31 - 1 (eg, the number of iterations before the  #
#     sequence repeats.                                                #
#   * Integers generated are non-repeating within the sequence and lie #
#     within the range 1 <= R <= 2147483647 [ 2^31 - 1 ]. Integers are #
#     returned uniformly distributed over the entire range.            #
#                                                                      #
# The public interface to this package are the following functions:    #
#                                                                      #
#   ----------------------------------------------------------------   #
#   * Randomize                                                        #
#     Randomize N                                                      #
#   Set a new seed for the random number generator. N (the new seed),  #
#   if supplied, must be greater than or equal to 1 and less than      #
#   2147483646. A good value might be your social security number. If  #
#   not supplied, the new seed is derived from the time by             #
#                                                                      #
#     N = time() % 2147483647 + 1                                      #
#                                                                      #
#   where time() returns the number of seconds since                   #
#   1 Jan 1970 00:00:00.                                               #
#                                                                      #
#   ----------------------------------------------------------------   #
#   * iRandom                                                          #
#     iRandom X                                                        #
#   Return the next pseudorandom integral number in the sequence. X,   #
#   if supplied, specifies the upper limit on the range of numbers to  #
#   be returned. It must be greater than or equal to 1 and less than   #
#   or equal to 2147483647. If not specified, X is assumed to be       #
#   2147483647.                                                        #
#                                                                      #
#   The returned value R is normalized such that 0 <= R < X. This      #
#   means that R is a member of the set (containing X elements)        #
#   { 0, 1, 2, ... , X-2 , X-1 }.                                      #
#                                                                      #
#   ----------------------------------------------------------------   #
#   * fRandom                                                          #
#   * fRandom X                                                        #
#   Return the next pseudorandom fractional (floating point) number    #
#   in the sequence. X, if supplied, specifies the upper limit on the  #
#   range of numbers to be returned. It must be greater than 0.0. If   #
#   not specified, X is assumed to be 1.0.                             #
#                                                                      #
#   The returned value R is normalized such that 0.0 <= R < X. R is    #
#   uniformly distributed over the entire range.                       #
#                                                                      #
#                                                                      #
# ==================================================================== #
# System Requirements:                                                 #
#                                                                      #
# This package should work correctly on all systems that support the   #
# following:                                                           #
#                                                                      #
#   * Fixed point (integer) arithmetic                                 #
#   Signed 32-bit or larger arithmetic is required. In particular, the #
#   target system must be able to represent 2147483647 (2^31 - 1) as   #
#   an integer value.                                                  #
#
#   * Floating point arithmetic:
#   The target system must represent floating point with a 46-bit (or
#   larger) mantissa, exluding the sign bit.
# ==================================================================== #
package random ;
use integer ;

# ==================================================================== #
# change the random number seed to X if supplied;                      #
# otherwise current time seeds it.                                     #
# ==================================================================== #
sub main::Randomize
{
  $argc = $#_ + 1 ; # argument count

  die "Constraint Failure (argument count)"
    unless ( 0 == $argc || 1 == $argc ) ;

  $X = ( 1 == $argc ? int( $_[0] ) : ( time() % $rand_max + 1 ) ) ;

  die "Constraint Failure (range)"
    unless ( $X >= 1 && $X <= $rand_max ) ;

  $seed = $X ;

Quote:
}

# ==================================================================== #
# return a random integer greater or equal to zero and less than X )   #
# ==================================================================== #
sub main::iRandom
{

  $argc = $#_ + 1 ; # argument count

  $X = int( $_[0] ) unless ( 0 == $argc ) ;

  die "Constraint failed (argument count)"
    unless ( 0 == $argc || 1 == $argc ) ;
  die "Constraint failed (range)"
    unless ( $X > 0 && $X <= $modulus ) ;

  $r  = random::Generate() ;

  $r = ( 0 == $argc ? $r : $r % $X ) ;

Quote:
}

# ==================================================================== #
# return a random floating point number ( greater than or equal to     #
# zero and less than X )                                               #
# ==================================================================== #
sub main::fRandom
{
  no integer ; # floating point division
...

read more »



Sat, 18 Jul 1998 03:00:00 GMT  
 srand and rand on NTPerl 5.001-1L-091

Quote:

> [Actual Perl Source]
> What happens in NTperl I can't say, but this would indicate
> that perl
> doesn't interfere much with the standard C library.

Hmmm, and knowing that it is fine on Linux, perhaps it's the
CLib used by the NTperl porters . . . hey, NTperl5 folx, what
compiler/version did you use?

-'f



Sat, 18 Jul 1998 03:00:00 GMT  
 srand and rand on NTPerl 5.001-1L-091


Quote:

>>Jeez, some people!

>Hmmmm.  *blinkblink*.

>Let me try again, from scratch:

>Hi, my name is Geoff Broadwell.  I'm trying to figure out where
>to address a major problem, and I'd even be willing to post the
>solution if need be.  I would like to know if the irrational
>behavior of srand() is a result of the way srand() and rand()
>are done in perl, in perl5, or in NTperl5 (in order of
>increasing specificity).

As far as I can tell in perl 4 and perl 5 srand just passes an integer
variable down to the C library srand, either converting the argument you
gave it to an int or using time to get the current time:

(perl 4.036)

    case O_SRAND:
        if (maxarg < 1) {
            (void)time(&when);
            anum = when;
        }
        else
            anum = (int)str_gnum(st[1]);
        (void)srand(anum);
        goto say_yes;

(perl 5.002b2)

PP(pp_srand)
{
    dSP;
    I32 anum;
    Time_t when;

    if (MAXARG < 1) {
        (void)time(&when);
        anum = when;
    }
    else
        anum = POPi;
    (void)srand(anum);
    EXTEND(SP, 1);
    RETPUSHYES;

Quote:
}

and srand is defined as void srand (unsigned int seed) on my alpha system.

What happens in NTperl I can't say, but this would indicate that perl
doesn't interfere much with the standard C library.

Hope this helps,

Mike

--
Mike Stok                        | The "`Stok' disclaimers" apply.


http://www.{*filter*}com.net/~stok/   | The inevitable WWW page (?)



Sat, 18 Jul 1998 03:00:00 GMT  
 
 [ 12 post ] 

 Relevant Pages 

1. Seed Randomization with srand() on Perl NT v5.001

2. use of rand and srand

3. rand and srand

4. srand or rand question

5. Broken rand() and srand() on perl5.005 ??

6. srand and rand fx

7. RAND/SRAND query

8. rand() and srand() busted on SVR4?

9. Help perl5.091.i86.zip

10. Answer: NTPerl is at ftp://ntperl.hip.com/ntperl/

11. Rand (or not to Rand)

12. Is rand() really rand ?

 

 
Powered by phpBB® Forum Software