🚀 go-pugleaf

In article <320@cubsvax.UUCP> peters@cubsvax.UUCP (Peter S. Shenkin) writes:
>In attempting to use these functions under 4.1bsd on a VAX/780, I found that
>rand() returns strictly alternating even and odd numbers, regardless of
>seed!!!  So I went and tried the same thing on a 4.2bsd system, and found
>the same behavior.  
>

If BSD rand() is at all like System V rand(), this is not a bug.  Rand()
is a multiplicitive congruential (sp?) random number generator, which means
it works like this:

        R    = A * R  + C  mod M
         i+1        i

So, depending on the parity of A and C, you have one of the following cases:

	Ri+1 is always odd
	Ri+1 is always even
	Ri+1 is always same parity as Ri
or	Ri+1 is always opposite parity of Ri

In this sort of number generator, the high bits are "more random" than the
low bits.  Thus, for example, to get a stream or random bits, one would
look at the top bit ( assuming M is a power of two... ), not the bottom bit.

Look at Knuth, Vol. II for almost all that is known on this topic.
-- 
Duty Now for the Future
					Tim Smith
			ihnp4!wlbr!callan!tim or ihnp4!cithep!tim

> In attempting to use these functions under 4.1bsd on a VAX/780, I found that
> rand() returns strictly alternating even and odd numbers, regardless of
> seed!!!  So I went and tried the same thing on a 4.2bsd system, and found
> the same behavior.  
> 
> It may be that this has already been hashed out in some
> of the above newsgroups, but since I only read net.lang.c among them I will
> have missed the discussion.  If anyone has a rewritten rand(), or other
> advice, I'd appreciate being mailed a fix.
> 
> Thanks,  Peter S. Shenkin,   {philabs,cmcl2!rna}!cubsvax!peters

rand uses a 32bit multiplicative random number generator.  These generators
tend to generate a repeating sequence in the lower bits.  On the pdp 11
the generator used a long and the returned value was shifted right by 16
bits to get an int.  The horribly behaved lower bits never hit the user.
On the vax the how 32 bit item is returned.  As you noticed those badly
behaved bits are there.  If you want to use rand shift it down.  Shift at
least 8 bits out.  A better way around the problem is to use the more
sophisticated random number generator random() all of its bits are supposed
to be random and its really not that much slower than rand().  A simple
#define rand random can fix your code.

My 'M' in <307@callan.UUCP> is meant to be even, by the way...
-- 
Duty Now for the Future
					Tim Smith
			ihnp4!wlbr!callan!tim or ihnp4!cithep!tim

> rand uses a 32bit multiplicative random number generator.  These generators
> tend to generate a repeating sequence in the lower bits.  On the pdp 11
> the generator used a long and the returned value was shifted right by 16
> bits to get an int.  The horribly behaved lower bits never hit the user.
> On the vax the how 32 bit item is returned.

Well, to be specific, on the VAX under 4.xBSD the 32 bit item is returned.
The System {III,V} systems still return the upper 16 bits.  This means that any
program that assumes "rand" returns something in the range 0 <= N < MAX16BITINT
will work on all UNIX systems on machines with 16-bit "int"s and on all System
N systems, but won't work right on 4.xBSD systems.  Grumble grumble...
-- 
	Guy Harris
	{seismo,ihnp4,allegra}!rlgvax!guy

> A better way around the problem is to use the more
> sophisticated random number generator random() all of its bits are supposed
> to be random and its really not that much slower than rand().  A simple
> #define rand random can fix your code.

  Our version of 4.2 random() ALWAYS returns an even number the first time it
is called after being seeded. That effectively breaks small applications
that call random only once.  (Or those that seed it for every call).

  	alexis

> > A better way around the problem is to use the more
> > sophisticated random number generator random() all of its bits are supposed
> > to be random and its really not that much slower than rand().  A simple
> > #define rand random can fix your code.
> 
>   Our version of 4.2 random() ALWAYS returns an even number the first time it
> is called after being seeded. That effectively breaks small applications
> that call random only once.  (Or those that seed it for every call).
> 
>   	alexis

The context of my bug fix was for applications that use many calls to rand
and don't want the pattern appearing in the low bits.

The question of generating a single number for an application such as fortune
is a different can of worms.  I don't deal with applications like fortune and
such but there is a reasonable way of doing them also.  The trick is to get
two seeds out of the environment somehow.  You can use the time, the number of
active jobs, the phase of the moon {don't have /dev/moon on your system? :-)}
and as much other crap as you can hash together.  Use one seed to seed the
random number generator.  Use the other to call the generator a few times.
Then get your random number from it.  Probably the only way to do better
is with a shot noise generator.  These don't generate lists.

The same bug in rand() appears on the VMS C compiler (VAX-11 C)!

When I reported it to DEC, they had never discovered it.

I happened to find it because I was using rand() to generate
a random noise graphic, and discovered an awful lot of pattern
in a supposedly randomly generated display.  What happened was
I made two successive calls to rand() to generate an x and y
coordinate, so all my x's fell on odd spaces, all my y's on
even.  Half the points were never chosen on my screen, and
a very regular half!

The fix was to call MTH$RANDOM on VMS, and random() on unix.
The moral:  compatible function libraries don't support compatible
systems when the original version was bugged!  Instead, they
support bugged, but compatible, code.  Equally wrong on VMS
or unix!!!

					-- Jon Krueger