peters@cubsvax.UUCP (Peter S. Shenkin) (03/01/85)
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!peterstim@callan.UUCP (Tim Smith) (03/05/85)
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
brooks@lll-crg.ARPA (Eugene D. Brooks III) (03/05/85)
> 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.
tim@callan.UUCP (Tim Smith) (03/05/85)
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
guy@rlgvax.UUCP (Guy Harris) (03/06/85)
> 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
alexis@reed.UUCP (Alexis Dimitriadis) (03/09/85)
> 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
brooks@lll-crg.ARPA (Eugene D. Brooks III) (03/12/85)
> > 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.