srand() troubles

[Merrill & Michele]

Many of us watched the World Series of Poker this last week and plotted how
we were to take over that world.

My current problem begins with shuffling the deck. For the apps I've
written before, I've always been satisfied with the usual:

#include <time.h>
#include <stdio.h>

int main( 2 things) {
time_t timer;
int tja;
srand(&timer);

tja=rand();
printf("%?", tja);
return(0);
}
The problem is that the time is always around 109 billion. This, in turn,
causes the generated pseudo-random to be around 23,000 with my
implementation. Even though I've been careful to slice up the 32768
outcomes of rand() in a reasoned way, the initial tilting has me wondering.
Two questions.
A) Do reasonable probabilists use rand(), given that you're not fooling
Gian Carlo Rota, but Chris Moneymaker?
B) If yes to A), then I think I'd want take that timer value, mask out the
things that don't change, maybe do a flip and an Xor, and then seed srand().
Does that sound like I'd then get values for the initial rand call with mu
around 16,000 and a bell curve?

 

[Ben Pfaff]

My current problem begins with shuffling the deck.

http://www.stanford.edu/~blp/writings/clc/shuffle.html
http://www.stanford.edu/~blp/writings/clc/random.html

 

[Keith Thompson]

Many of us watched the World Series of Poker this last week and plotted how
we were to take over that world.

My current problem begins with shuffling the deck. For the apps I've
written before, I've always been satisfied with the usual:

#include <time.h>
#include <stdio.h>

int main( 2 things) {
time_t timer;
int tja;
srand(&timer);

tja=rand();
printf("%?", tja);
return(0);
}

Show us real code. We can't guess how your pseudo-code differs from
the code you actually compiled.

The problem is that the time is always around 109 billion. This, in turn,
causes the generated pseudo-random to be around 23,000 with my
implementation. Even though I've been careful to slice up the 32768
outcomes of rand() in a reasoned way, the initial tilting has me wondering.

Don't assume that there are 32768 possible values; use RAND_MAX.

Two questions.
A) Do reasonable probabilists use rand(), given that you're not fooling
Gian Carlo Rota, but Chris Moneymaker?
B) If yes to A), then I think I'd want take that timer value, mask out the
things that don't change, maybe do a flip and an Xor, and then seed srand().
Does that sound like I'd then get values for the initial rand call with mu
around 16,000 and a bell curve?

The standard guarantees a few things about the behavior of rand() and
srand(), but much of their behavior is implementation-defined. For
example, it's not uncommon for rand() to return alternating odd and
even numbers. Many implementations provide higher quality random
number generators.

There's also some good information in section 13 of the C FAQ,
<http://www.eskimo.com/~scs/C-faq/faq.html>.

 

[Keith Thompson]

Thanks both. The chance of me being able to reproduce code on a console
that does anything except draw scorn from a compiler is vanishingly small.
Furthermore, your output will be different from mine as a matter of
cosmology. I've attached a screen dump that shows the situation without
showing too much bad programming form. (Do people prefer to see code pasted
into the body of a message or as an attachment?)

Attachments are strongly discouraged, binary attachments even more so.
If you want to post a code sample, paste it into the body of your
message. If at all possible, post a small self-contained compilable
program. Take a look at some of the other articles in the newsgroup
to get an idea of how things are done around here.

If you're really unable to create compilable C code, I'm afraid you
may not be ready for us to help you. Learn the basics of the language
first. Kernighan & Ritchie's _The C Programming Language_, 2nd
edition, is widely considered to be one of the best tutorials. Work
through the exercises.

Going back to the pseudo-code you posted earlier, you had:

time_t timer;

srand(&timer);

srand() expects an unsigned int argument; you're passing it the
address of a time_t variable, which makes no sense. If your compiler
doesn't warn you about this, either it's a really bad compiler, or

I had no idea that I could have other than 2^15 outcomes. How often is this
the case, given that I'm not ever going to play Texas Hold'em with an
embedded system? MPJ

Your system should have documentation for the standard library
functions, include srand() and rand(). If you can't find that,
consult any decent C textbook or do a web search. And I already
pointed you to the C FAQ.

A quick summary:

srand() takes an unsigned int argument which is used as the seed for a
sequence of pseudo-random numbers. It should normally be called
exactly once in your program, before any calls to rand(). The call
srand(time(NULL));
is often good enough (but *only* if the appropriate headers are
included).

rand() takes no arguments, and returns an int result. The result is a
pseudo-random integer in the range 0 to RAND_MAX. RAND_MAX is
guaranteed to be at least 32767.

 

[Guillaume]

Many implementations of rand() are extremely poor.
And the Microsoft's one is particularly hideous. It just isn't suitable
for anything else that toying around.

I suggest you read Knuth's Seminumerical Algorithms to begin with.

 

[Merrill & Michele]

Thanks both. The chance of me being able to reproduce code on a console

small.

Attachments are strongly discouraged, binary attachments even more so.

Thank you again for your thoughtful response. My shortcomings with
srand(time(&timer)) were amended in my binary attachment, which, along with
the .eml it came with, seems to have disappeared. Anscheinend ist Ashcroft
nicht der Einzige, der mir die Post verweigert Is the no binaries policy
to keep the porno punks out?

What to do? I won't read K&R. I did pay $2^5 for the last book I bought on
comp sci. I would like to announce that my demographic and I would gladly
pay $2^6 for a book entitled: Essential Knuth in C. MPJ

 

[Keith Thompson]

Thank you again for your thoughtful response. My shortcomings with
srand(time(&timer)) were amended in my binary attachment, which, along with
the .eml it came with, seems to have disappeared. Anscheinend ist Ashcroft
nicht der Einzige, der mir die Post verweigert Is the no binaries policy
to keep the porno punks out?

Many of us use newsreaders that don't support binary attachments.
There are newsgroups for binaries; many servers don't carry them
because of the huge bandwidth and storage requirements. This is a
discussion forum. If you want the web, you know where to find it.

What to do? I won't read K&R. I did pay $2^5 for the last book I bought on
comp sci. I would like to announce that my demographic and I would gladly
pay $2^6 for a book entitled: Essential Knuth in C. MPJ

You won't read K&R? Why on Earth not? I find it difficult to believe
that anyone who refuses to read K&R is at all serious about learning C.

 

[CBFalconer]

.... snip ...
cosmology. I've attached a screen dump that shows the situation
without showing too much bad programming form. (Do people prefer
to see code pasted into the body of a message or as an attachment?) .... snip ...

Name: ccode1.JPG
ccode1.JPG Type: JPEG Image (image/jpeg)
Encoding: x-uuencode

NEVER attach a binary to a usenet message. In fact, never attach
anything. Cut your code down to the minimum to show the problem,
and remain compilable (not over about 100 lines) and paste that
into the message.

 

[Merrill & Michele]

You won't read K&R? Why on Earth not? I find it difficult to believe

that anyone who refuses to read K&R is at all serious about learning C.

I can't imagine you're interested in my biography, but I'll tell you a
little bit about it. I used to be a champion speller. Then I became
bilingual, trilingual, learned basic, pascal, fortran, c and so forth (not
in that order). Now I can't spell. It turns out, when you know the
Mittelhochdeutsch and go cross-eyed in cyrillic, it's a one-way street to
missing skills one formerly had.

K&R have **plenty** of influence around here. If the absent demigods want
to step up and be leaders, now would be a good time. MPJ

P.S. My apologies in advance if K or R is unwell.

 

[Ben Pfaff]

I can't imagine you're interested in my biography, but I'll tell you a
little bit about it. I used to be a champion speller. Then I became
bilingual, trilingual, learned basic, pascal, fortran, c and so forth (not
in that order). Now I can't spell. It turns out, when you know the
Mittelhochdeutsch and go cross-eyed in cyrillic, it's a one-way street to
missing skills one formerly had.

K&R have **plenty** of influence around here. If the absent demigods want
to step up and be leaders, now would be a good time. MPJ

P.S. My apologies in advance if K or R is unwell.

I nominate the above for "Weird comp.lang.c Article of the Month".

 

[Jim]

I nominate the above for "Weird comp.lang.c Article of the Month".

Seconded.

 

[Keith Thompson]

I can't imagine you're interested in my biography, but I'll tell you a
little bit about it. I used to be a champion speller. Then I became
bilingual, trilingual, learned basic, pascal, fortran, c and so forth (not
in that order). Now I can't spell. It turns out, when you know the
Mittelhochdeutsch and go cross-eyed in cyrillic, it's a one-way street to
missing skills one formerly had.

K&R have **plenty** of influence around here. If the absent demigods want
to step up and be leaders, now would be a good time. MPJ

P.S. My apologies in advance if K or R is unwell.

What that supposed to be meaningful?

 

[Randy Howard]

I nominate the above for "Weird comp.lang.c Article of the Month".

And a candidate for the year for sure.

 

[Chris Barts]

Is the no binaries policy to keep the porno punks out?

Surprisingly little pornography filters into the comp. hierarchy. ;-)
Attachments are often dropped somewhere along the line anyway (and, thus,
aren't guaranteed to reach everyone), and binary attachments are
frequently huge chunks of junk that don't even work on all systems (you
should only need a text terminal to enjoy this newsgroup).

What to do? I won't read K&R. I did pay $2^5 for the last book I bought on
comp sci.

$32 is not a bad price for a good book. (The fact that most programming
books are crap is a different topic.)

I would like to announce that my demographic and I would gladly
pay $2^6 for a book entitled: Essential Knuth in C. MPJ

Knuth is best grasped free of the accidental limitations of any specific
language. He focuses on algorithm design, and any primitive-recursive
algorithm can be expressed in any Turing-complete language. There's a huge
advantage to decoupling algorithms from implementations.

(Plus, C is full of accidental limitations, related to the low-level
semantics and the popularity of nonstandard extensions. Another great
book, "Structure and Interpretation of Computer Programs", uses Scheme (a
minimalistic Lisp dialect) as its pedagogical tool, but its focus is
different from Knuth's books.)

 

[Ben Pfaff]

$32 is not a bad price for a good book. (The fact that most programming
books are crap is a different topic.)

We're in comp.lang.c, so he only paid $7, a real bargain. Must
have been a used copy.

 

[Default User]

you a >> little bit about it. I used to be a champion speller. Then
I became >> bilingual, trilingual, learned basic, pascal, fortran, c
and so forth (not >> in that order). Now I can't spell. It turns
out, when you know the >> Mittelhochdeutsch and go cross-eyed in
cyrillic, it's a one-way street to >> missing skills one formerly had.

Seconded.

All in favor, say aye.

Aye!




Brian

 

[Merrill & Michele]

snip

$32 is not a bad price for a good book. (The fact that most programming
books are crap is a different topic.)

Scott Nudds flies out of somebody's hard drive last week and my lamentation
of the lack of goals and direction for this forum and this language are
going to win a "weird" award? I'd bet dollars to donuts that my wholesale
detractors don't know mittelhoch from windloch.

Knuth is best grasped free of the accidental limitations of any specific
language. He focuses on algorithm design, and any primitive-recursive
algorithm can be expressed in any Turing-complete language. There's a huge
advantage to decoupling algorithms from implementations.

(Plus, C is full of accidental limitations, related to the low-level
semantics and the popularity of nonstandard extensions. Another great
book, "Structure and Interpretation of Computer Programs", uses Scheme (a
minimalistic Lisp dialect) as its pedagogical tool, but its focus is
different from Knuth's books.)

Thank you for your response. Certainly, one recognizes the value of
algorithms in "programmese." I just find too many gotchas on the road to
getting those programs running on my implementation. srand() is a good
example. I thought I was being all kinds of clever to determine whether the
numbers 0 and 32767 turned up on ensuing rand() calls. I would have
blithely assumed that my code would port in complete ignorance of RAND_MAX.
I doubt that Knuth addresses this, and if K&R does, here's your chance to
say I told you so.

C has limitations, as any language must. I would make the analogy that it
is like Russia, which "the world" shifted away from but now looks poised
very nicely and has extraordinary assests. I'll take a look at that book.
MPJ

 

[pete]

srand() is a good example.
I thought I was being all kinds of clever to determine whether the
numbers 0 and 32767 turned up on ensuing rand() calls. I would have
blithely assumed that my code would port in complete
ignorance of RAND_MAX.
I doubt that Knuth addresses this, and if K&R does,
here's your chance to say I told you so.

K&R2, APPENDIX B, p.252

int rand(void)
rand returns a psuedo-random integer in the range of 0 to RAND_MAX,
which is at least 32767.

 

[Gordon Burditt]

My current problem begins with shuffling the deck. For the apps I've

written before, I've always been satisfied with the usual:

#include <time.h>
#include <stdio.h>

int main( 2 things) {
time_t timer;
int tja;
srand(&timer);

tja=rand();
printf("%?", tja);
return(0);
}
The problem is that the time is always around 109 billion. This, in turn,

You're passing the address of timer, not its value, to srand().

causes the generated pseudo-random to be around 23,000 with my
implementation. Even though I've been careful to slice up the 32768
outcomes of rand() in a reasoned way, the initial tilting has me wondering.
Two questions.
A) Do reasonable probabilists use rand(), given that you're not fooling
Gian Carlo Rota, but Chris Moneymaker?

If, indeed, on your system RAND_MAX is 32768, it isn't all that
unreasonable for someone to look at the cards in his own hand
(including the order the cards were dealt), figure out all the
possible 32768 shuffles, and know what's in everyone's hand and the
rest of the deck (a precomputed index helps here). For that matter,
even if RAND_MAX is 2^31, the number of possible shuffles with the
random number generator is a LOT less than the number of possible
shuffles with a physical deck.

B) If yes to A), then I think I'd want take that timer value, mask out the
things that don't change, maybe do a flip and an Xor, and then seed srand().

If you limit the possible seeds to below RAND_MAX, the number of
possible shuffles gets even lower, and more predictable. I'd want
to use a high-resolution timer (preferably nanoseconds or finer)
and hardware designed to give true random values based on
quantum-mechanical principles (thermal noise, radioactive decay
measurements, etc.). None of this is available in Standard C. And
I'd probably want to use a random number generator for which RAND_MAX
and the number of possible seed values is is a lot greater than 52
factorial. 256 bits might be enough.

Does that sound like I'd then get values for the initial rand call with mu
around 16,000 and a bell curve?

Gordon L. Burditt

 

[CBFalconer]

If, indeed, on your system RAND_MAX is 32768, it isn't all that
unreasonable for someone to look at the cards in his own hand
(including the order the cards were dealt), figure out all the
possible 32768 shuffles, and know what's in everyone's hand and
the rest of the deck (a precomputed index helps here). For that
matter, even if RAND_MAX is 2^31, the number of possible shuffles
with the random number generator is a LOT less than the number of
possible shuffles with a physical deck.


If you limit the possible seeds to below RAND_MAX, the number of
possible shuffles gets even lower, and more predictable. I'd
want to use a high-resolution timer (preferably nanoseconds or
finer) and hardware designed to give true random values based on
quantum-mechanical principles (thermal noise, radioactive decay
measurements, etc.). None of this is available in Standard C.
And I'd probably want to use a random number generator for which
RAND_MAX and the number of possible seed values is is a lot
greater than 52 factorial. 256 bits might be enough.

The following is an extract from a file available in my hashlib
package, and used to automate the testing code. The package is
available at:

<http://cbfalconer.home.att.net/download/>

/* FILE cokusmt.c */
/* This is a miniscule cleanup of the source downloaded from: */
/* http://www.math.keio.ac.jp/~matumoto/ver980409.html */

/* This is the "Mersenne Twister" random number generator MT19937,
// which generates pseudorandom integers uniformly distributed in
// 0..(2^32 - 1) starting from any odd seed in 0..(2^32 - 1). This
// version is a recode by Shawn Cokus ([email protected])
// on March 8, 1998 of a version by Takuji Nishimura (who had
// suggestions from Topher Cooper and Marc Rieffel in July-August
// 1997).
//
.... snip ...
//
// From URL <http://www.math.keio.ac.jp/~matumoto/emt.html> (and
// paraphrasing a bit in places), the Mersenne Twister is
// "designed with consideration of the flaws of various existing
// generators," has a period of 2^19937 - 1, gives a sequence
// that is 623-dimensionally equidistributed, and "has passed
// many stringent tests, including the die-hard test of G.
// Marsaglia and the load test of P. Hellekalek and S.
// Wegenkittl." It is efficient in memory usage (typically using
// 2506 to 5012 bytes of static data, depending on data type
// sizes, and the code is quite short as well). It generates
// random numbers in batches of 624 at a time, so the caching and
// pipelining of modern systems is exploited. It is also divide-
// and mod-free. */

Now my suggestion is to use the (normally pitiful) built in rand
and srand functions to produce one random value, and use the
result to seed the Mersenne Twister (with seedMT()). You could
then use another value from rand to clock the twister through a
semi-random number of initial values, and continue from there.
Something like:

unsigned long count;

srand(time(NULL));
seedMT((unsigned long)rand() & ~1UL);
count = rand();
while (count--) randMT();

This only need to happen once, at program initialization, and can
be bypassed for a deterministic sequence for testing. After that
the shuffle can depend only on randMT. If initialization takes
too long limit the size of count.

Notice that the period of the Mersenne Twister is much longer than
the maximum return value, which is ULONG_MAX. Thus duplicate
values CAN and will occur.