Random is strange

[Phil Carmody]

Better would be

int rand_less_than_n(int n) {
int r;
while ((r = rand()) < ((RAND_MAX % n) + 1) % n) ;
return r % n;
}

The double-mod is to handle the (common) case where RAND_MAX == INT_MAX,
so that RAND_MAX+1 would overflow an int.

If n-1 > RAND_MAX you've got problems anyway, so why not
just pull everything down by n before doing the %?

while ((r = rand()) < (((RAND_MAX-(n-1)) % n) { ; }

Phil

 

[maverik]

The trouble is, many real-world C implementations *do* have poor
rand() functions, perhaps partly because the C standard provides a
sample implementation.  Certainly a rand() implementation should be as
good as possible, but I'm not going to reject an implementation just
because its rand() is poor.  Many implementations provide alternate
PRNGs, typically ones that don't fit into the standard's requirements
for rand() and srand().

Disclaimer: I don't actually know what the current state of rand()
implementations is.  If I'm wrong, if most or all existing
implementations have been enhanced so the low-order bits are as good
as the high-order bits, then my argument is weakened.  Does anyone
know the actual current state of the art?  Do any existing
implementations still use the sample implementation given in the C
standard?

Hi, Keith.

I saw last libc sources (http://sources.redhat.com/glibc/)

/* If we are using the trivial TYPE_0 R.N.G., just do the old linear
congruential bit. Otherwise, we do our fancy trinomial stuff, which
is the same in all the other cases due to all the global variables
that have been set up. The basic operation is to add the number at
the rear pointer into the one at the front pointer. Then both
pointers are advanced to the next location cyclically in the table.
The value returned is the sum generated, reduced to 31 bits by
throwing away the "least random" low bit.

Note: The code takes advantage of the fact that both the front and
rear pointers can't wrap on the same call by not testing the rear
pointer if the front one has wrapped. Returns a 31-bit random
number. */

int
__random_r (buf, result)
struct random_data *buf;
int32_t *result;
{
int32_t *state;

if (buf == NULL || result == NULL)
goto fail;

state = buf->state;

if (buf->rand_type == TYPE_0)
{
int32_t val = state[0];
val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
state[0] = val;
*result = val;
}
else
{
int32_t *fptr = buf->fptr;
int32_t *rptr = buf->rptr;
int32_t *end_ptr = buf->end_ptr;
int32_t val;

val = *fptr += *rptr;
/* Chucking least random bit. */
*result = (val >> 1) & 0x7fffffff;
++fptr;
if (fptr >= end_ptr)
{
fptr = state;
++rptr;
}
else
{
++rptr;
if (rptr >= end_ptr)
rptr = state;
}
buf->fptr = fptr;
buf->rptr = rptr;
}
return 0;

fail:
__set_errno (EINVAL);
return -1;
}

and by default TYPE_3 is set:

static struct random_data unsafe_state =
{
[snip]

/* The following things are the pointer to the state information
table,
the type of the current generator, the degree of the current
polynomial
being used, and the separation between the two pointers.
Note that for efficiency of random, we remember the first location
of
the state information, not the zeroth. Hence it is valid to access
state[-1], which is used to store the type of the R.N.G.
Also, we remember the last location, since this is more efficient
than
indexing every time to find the address of the last element to see
if
the front and rear pointers have wrapped. */

.state = &randtbl[1],

.rand_type = TYPE_3,
.rand_deg = DEG_3,
.rand_sep = SEP_3,

.end_ptr = &randtbl[sizeof (randtbl) / sizeof (randtbl[0])]
};

 

[Nate Eldredge]

If n-1 > RAND_MAX you've got problems anyway, so why not
just pull everything down by n before doing the %?

while ((r = rand()) < (((RAND_MAX-(n-1)) % n) { ; }

Phil

Yep, that works too. I just wanted to point out that

while ((r = rand()) < (RAND_MAX + 1) % n) ; /* bad */

didn't.

 

[lawrence.jones]

The trouble is, many real-world C implementations *do* have poor
rand() functions, perhaps partly because the C standard provides a
sample implementation.

A *few* real-world C implementations have poor rand() functions, because
they do *not* use the sample implementation from the standard, which is
a decent, albeit only 16 bit, generator. The truly abysmal
implementations use the sample implementation but without the division
(or shift) that returns the high-order bits of the internal state and
instead just return the entire state, whose low-order bits *are*
distressingly non-random. That particularly unfortunate "enhancement"
came from UCB around the 4.2 timeframe and was included in the Net 2
release, so it was widely distributed, but it has been mostly stamped
out in the intervening years.

 

[CBFalconer]

I consider that "time(NULL)" stands for the time when the program
executes. In my opinion each time the rand() should get different
result.For example,
5+4=9
2+6=8
3+4=7
The player lost.
But actually it stays the same while I place the sentence
( srand(time (NULL)) )among the module. I cannot understand.

Rand always returns the NEXT in a series of random numbers. That
series always begins at the same point on program startup, unless
initialized by a call to srand. Thus you want to call srand
exactly once, and do it before executing any calls to rand.

If you want to post a followup via groups.google.com, ensure you
quote enough for the article to make sense. Google is only an
interface to Usenet; it's not Usenet itself. Don't assume your
readers can, or ever will, see any previous articles.

More details at: <http://cfaj.freeshell.org/google/>

 

[James Dow Allen]

a program like you's will run very quickly....
It is simply using the same time over and over again....

The one type of comment universally agreed to be on-topic
here is discussion of (non-)topicality, so let me ask:

Would it not be non-topical for me to point out that
the S370 clock was *guaranteed* to increment between calls
(indeed lower-end 370's sometimes had microcode NOP's to guarantee
this)? This is a useful feature (although obviously irrelevant
to Jenny if she would just RT(F)M).

And would it not also be non-topical for me to point out
that this preferred S370 behavior is Yet Another Example(tm)
that computer designers from the Jurassic Era weren't *quite*
as moronic as uppity hip-hoppers believe? Indeed that
evidence is accumulating from events in the post-literate
world that literacy wasn't such a bad idea after all?

Ahhh ... nevermind.

James

 

[Andrew Smallshaw]

If the C library is broken is not the job of every application to work
around it. (rand() % 6 + 1) is the correct way to get a non-secure but
reasonably random number between 1 and 6.

I agree with this in part. The "faulty" RNGs in question are indeed
particularly problematic for many common cases and _should_ be
fixed. However, the fact that a particular implementation does
not work well with a particular application is not in itself evidence
that the RNG in question is fundamentally flawed. RNGs are by
their very nature unpredictable. By this I don't mean the sequence
of the numbers but their interaction with the surrounding application.
I have had problems with RNGs in the past because a magic constant
in the implementation happened to be a factor of the size of a data
structure in my application. Such interactions are difficult to
predict but can potentially occur for any purely software implementation
becasue the numbers themselves must be systematic in _some_ manner.

Then of course there is how good a random number is needed. If
all that is needed is something cheap and cheerful to give a certain
level of unpredictability then any old RNG will do. If your
requirements are more involved then something more leaborate may
be need, but such an RNG may well be more computationally expensive.
Personally I only really expect the standard library function to
be a basic implementation for undemanding applications. For
something more important then greater care is needed.

Ultimately if an RNG fails to perform in a particular case it is
not the fault of the implementation, it is the fault of the programmer
in failing to perform an adequate level of testing and QA. RNGs
are not fungible off-the-shelf commodities and if their performance
is crucial then they should not be regarded as such.

 

[Old Wolf]

 I consider that "time(NULL)" stands for the time when the program
executes. In my opinion each time the rand() should get different
result.But actually it stays the same while I place the sentence( srand
(time(NULL)) )among the module

time(NULL) usually gives you a number of seconds.

If you keep calling it quickly in succession, you
will get the same number back (until a full second
has passed!)

That is why you keep getting the same result when
you place it so that it gets called quickly in succession.

 

[CBFalconer]

The one type of comment universally agreed to be on-topic
here is discussion of (non-)topicality, so let me ask:

Would it not be non-topical for me to point out that the S370
clock was *guaranteed* to increment between calls (indeed
lower-end 370's sometimes had microcode NOP's to guarantee
this)? This is a useful feature (although obviously
irrelevant to Jenny if she would just RT(F)M).

And wouldn't it be considerably simpler to simply refer 'Jenny' to
an appropriate newsgroup dealing with IBMery? Meanwhile I could
point out that 370's sometimes incremented their clock at
completely random times. I might very well be wrong, but what do
you expect on c.l.c?