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]

"Merrill & Michele" <be********@comcast.net> writes:

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
--
"...Almost makes you wonder why Heisenberg didn't include postinc/dec operators
in the uncertainty principle. Which of course makes the above equivalent to
Schrodinger's pointer..."
--Anthony McDonald

[Keith Thompson]

"Merrill & Michele" <be********@comcast.net> writes:

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 (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Keith Thompson]

"Merrill & Michele" <be********@comcast.net> writes:

Show us real code. We can't guess how your pseudo-code differs from
the code you actually compiled.
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
you're missing a "#include <stdlib.h>" directive, or you've suppressed
or ignored diagnostic messages somehow.
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.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[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

that does anything except draw scorn from a compiler is vanishingly

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

-----
All right
Send lawyers, guns and money
Huh!
--Warren Zevon

[Keith Thompson]

"Merrill & Michele" <be********@comcast.net> writes:

> 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.

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?

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.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[CBFalconer]

Merrill & Michele wrote:

.... 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.

--
"This is a wonderful answer. It's off-topic, it's incorrect,
and it doesn't answer the question." -- Richard Heathfield

"I support the Red Sox and any team that beats the Yankees"

[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]

"Merrill & Michele" <be********@comcast.net> writes:

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".
--
Ben Pfaff
email: bl*@cs.stanford.edu
web: http://benpfaff.org

[Jim]

On Thu, 16 Sep 2004 21:23:17 -0700, Ben Pfaff <bl*@cs.stanford.edu>
wrote:

"Merrill & Michele" <be********@comcast.net> writes:

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".

Seconded.

[Keith Thompson]

"Merrill & Michele" <be********@comcast.net> writes:

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.

What that supposed to be meaningful?

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Randy Howard]

In article <87************@benpfaff.org>, bl*@cs.stanford.edu says...

"Merrill & Michele" <be********@comcast.net> writes:

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".

And a candidate for the year for sure.
--
Randy Howard (To reply, remove FOOBAR)

[Chris Barts]

On Thu, 16 Sep 2004 17:47:27 -0500, Merrill & Michele wrote:

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]

Chris Barts <ch*****@gmail.com> writes:

On Thu, 16 Sep 2004 17:47:27 -0500, Merrill & Michele wrote:

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.)

We're in comp.lang.c, so he only paid $7, a real bargain. Must
have been a used copy.
--
"In My Egotistical Opinion, most people's C programs should be indented six
feet downward and covered with dirt." -- Blair P. Houghton

[Default User]

Jim wrote:

On Thu, 16 Sep 2004 21:23:17 -0700, Ben Pfaff <bl*@cs.stanford.edu>
wrote:

"Merrill & Michele" <be********@comcast.net> writes:

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".

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.)

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

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]

Merrill & Michele wrote:

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.

--
pete

[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]

Gordon Burditt wrote:

My current problem begins with shuffling the deck. For the apps
I've written before, I've always been satisfied with the usual:
.... snip ...
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 foolingGian 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 thethings 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?

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 (Co***@math.washington.edu)
// 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.

--
"This is a wonderful answer. It's off-topic, it's incorrect,
and it doesn't answer the question." -- Richard Heathfield

"I support the Red Sox and any team that beats the Yankees"

[Gordon Burditt]

>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
The number of possible shuffles of a deck of cards is 52 factorial.
Any seed less than 200 bits long is pitifully inadequate, especially
if you're playing for real money.

By using the built in rand() to generate a seed, you are potentially
crippling the Mersenne Twister (which only has 31 bits of seed,
still horribly inadequate, but probably generates much better random
numbers than rand()) with something which may only generate 2**15
possible seeds.
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.
This approach does nothing to increase the number of possible shuffle
results beyond the number of seeds that srand() accepts.
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.

This would increase the number of possible shuffles *IF* you don't
start the program over again each time, but just continue from
the previous state of the Twister.

Gordon L. Burditt

[Merrill & Michele]

Thanks all. I'll go with the Twister. Just seeing the word Mersenne in it
and having it associated with Knuth is sufficient for me to invest my faith
in it. I'm worried about design already, but that is not germane to this
thread.

Can you imagine having been in the room when Frank Coles wordlessly
approached the board and wrote:
2^67-1=193707721*761838257287 ? MPJ

[CBFalconer]

Gordon Burditt wrote:

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

The number of possible shuffles of a deck of cards is 52 factorial.
Any seed less than 200 bits long is pitifully inadequate, especially
if you're playing for real money.

By using the built in rand() to generate a seed, you are potentially
crippling the Mersenne Twister (which only has 31 bits of seed,
still horribly inadequate, but probably generates much better random
numbers than rand()) with something which may only generate 2**15
possible seeds.

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.

This approach does nothing to increase the number of possible shuffle
results beyond the number of seeds that srand() accepts.

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.

This would increase the number of possible shuffles *IF* you don't
start the program over again each time, but just continue from
the previous state of the Twister.

That is assumed. Note that shuffling a deck requires only 52
successive random values (assuming no rejections by the shuffling
code). Once the system has been seeded the future shuffles are
deterministic, but I challenge anybody to create a practical way
of detecting the seed from a reasonable deal. The period of
2^19937 -1 makes indexing this impracticable. The seed of the
built in rand probably cannot be detected, because its values are
only used twice.

--
"This is a wonderful answer. It's off-topic, it's incorrect,
and it doesn't answer the question." -- Richard Heathfield

"I support the Red Sox and any team that beats the Yankees"

[Gordon Burditt]

>That is assumed. Note that shuffling a deck requires only 52

successive random values (assuming no rejections by the shuffling
code). Once the system has been seeded the future shuffles are
deterministic, but I challenge anybody to create a practical way
of detecting the seed from a reasonable deal. The period of
2^19937 -1 makes indexing this impracticable. The seed of the
built in rand probably cannot be detected, because its values are
only used twice.

I only need to determine
(a) the initial seed to srand(), and
(b) which shuffle we are on since the program restarted.
everything is determined from that.

Given those two items, I just need to run the algorithm forward,
which should be trivial if the machine is playing against a human
(with a hidden computer, or talking to someone with a computer) who
is expected to take time for his decisions.

Now, how do I determine (a) and (b)? Run the algorithm forward for
all possible combinations of seeds and maybe the first dozen or so
shuffles from any start of the program. (Note: it really helps
here if I can force the program to restart, as in cause a power
failure, say overnight, to go back to deal 1, so when I get to the
machine the deal number is "small"). Make an index of things I can
observe (cards I get dealt) to look up (a) and (b). This I only
have to do once, and store it.

Then I feed in observed items for this deal, and see how many
possibilities there are. Once I know that the seed is X and the
shuffle is N, the next deal is either seed X and shuffle N+1 or
unknown seed and shuffle 1.

If the initial seed only has 15 bits and you compute 30 deals, the
precomputed index is probably feasable with only about 1 million
entries. (and possibly could be done with a handheld). The index
perhaps includes my 5 cards (6 bits each), in order, the seed (16
bits), and the deal number (8 bits) - about 7MB total. The 5 cards
you see have 300 million possible combinations (including the order,
which you should use if it's available), so most of the time ( 316
out of 317) you should be able to identify a unique seed and deal
from just your own cards. There's also a substantial chance that
you will be able to tell that your combination is not in the index
(the machine has been running longer than 30 deals) if that's the
case. I believe this is a practical way to determine the seed from
part of the dealt cards (for the 15-bit seed case).

If the initial seed has 31 bits (and you do 30 deals), the index
is now getting large enough that it takes lots of storage and it
may be hard to get answers fast enough. Further, you almost certainly
will not be able to identify a unique seed and deal from your own
5 cards (you'll probably end up with about 200 possibilities). You
still might be able to determine the seed and deal AFTER the hand
is played and then determine the next hand. You also won't be able
to tell if your combination is not in the index. Given, say, 5
possible shuffles, equally likely, quick, determine how you should
bet. Unless you get really serious about this, and are able to do
it unobserved (say, over the internet or at an unattended poker
machine in a store (not casino)) and observe several hands first,
this isn't a practical way to determine the seed.

The huge state kept by the Twister (period of 2**19937 -1) is
sabotaged by the limited seed and practical limits on the run time
of the program.

Gordon L. Burditt

[CBFalconer]

Gordon Burditt wrote:

That is assumed. Note that shuffling a deck requires only 52
successive random values (assuming no rejections by the shuffling
code). Once the system has been seeded the future shuffles are
deterministic, but I challenge anybody to create a practical way
of detecting the seed from a reasonable deal. The period of
2^19937 -1 makes indexing this impracticable. The seed of the
built in rand probably cannot be detected, because its values are
only used twice.
I only need to determine
(a) the initial seed to srand(), and
(b) which shuffle we are on since the program restarted.
everything is determined from that.

Given those two items, I just need to run the algorithm forward,
which should be trivial if the machine is playing against a human
(with a hidden computer, or talking to someone with a computer) who
is expected to take time for his decisions.

Now, how do I determine (a) and (b)? Run the algorithm forward for
all possible combinations of seeds and maybe the first dozen or so
shuffles from any start of the program. (Note: it really helps
here if I can force the program to restart, as in cause a power
failure, say overnight, to go back to deal 1, so when I get to the
machine the deal number is "small"). Make an index of things I can
observe (cards I get dealt) to look up (a) and (b). This I only
have to do once, and store it.

Then I feed in observed items for this deal, and see how many
possibilities there are. Once I know that the seed is X and the
shuffle is N, the next deal is either seed X and shuffle N+1 or
unknown seed and shuffle 1.

.... snip ...
The huge state kept by the Twister (period of 2**19937 -1) is
sabotaged by the limited seed and practical limits on the run time
of the program.

Not being any sort of cryptographer, I guess you are right in that
it can be beaten. After all, there is no such thing as an
unbeatable system, given enough time. Another thought that occurs
to me is to permute the bit order of the randoms generated.
However, all this is getting OT here, where the original idea was
to generate a suitable simile of a shuffle, not to protect it
against the world.

--
"This is a wonderful answer. It's off-topic, it's incorrect,
and it doesn't answer the question." -- Richard Heathfield

"I support the Red Sox and any team that beats the Yankees"

[Mike Wahler]

"Default User" <fi********@boeing.com.invalid> wrote in message
news:I4********@news.boeing.com...

Jim wrote:

On Thu, 16 Sep 2004 21:23:17 -0700, Ben Pfaff <bl*@cs.stanford.edu>
wrote:

"Merrill & Michele" <be********@comcast.net> writes:

> 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".

Seconded.

doubled;
All in favor, say aye.

int i;

-Mike