Rand() with base

[Arthur J. O'Dwyer]

The way I do it now is to save the whole tilebag. It would be nice to have
an integer that I could use to re-create the same game. I was working in
some kind of hash function. I thought the rand() function used the system
time or something to change each number, each time you called it. I'm a
little surprised it can be so predictable.

'rand' has to be predictable; otherwise, how could you ever test it
for correctness? Besides, the system timer is a notoriously bad way of
getting true random bits; if the C standard library seemed to bless it
in any way, that would just encourage bad security products. And Unix
(C's natural habitat takes its security *very* seriously.

If you want true randomness, there exist RNG servers for such
purposes, online. But then you can't use portable C to get online,
so it's OT either way.

A 16bit number would be OK, but maybe I should string a couple of rand()
generated numbers together.

Has anyone played with bitshifting and XOR'ing several rands to make them
more random, or perhaps XOR with the current time/date?

srand((unsigned)time(0)) is the "canonical" way to get a random seed
into the PRNG. Of course it's not secure, but it's good enough for
games and things that you won't ever need to run twice in close succession
expecting different outputs.

Something like put a rand() (15bit) into a 64bit number, shift a random
amount (<64bit), XOR or even "&" with another rand, loop again "X" times...

You are describing the "hashing" of a random number. This is the
second law of thermodynamics speaking: No matter how much you screw
around with a random variable, it's not gonna get any more random.
It can get *less* random, of course (shifting bits off the end will
lose those bits forever, e.g.), but you can't make randomness (a.k.a.
"information"; perversely, these are basically the same thing at the
information-theory level) from nothing.
Take further discussion of random numbers, security, and information
theory to one of comp.programming or sci.crypt, please.

-Arthur

 

[Jack Klein]

The way I do it now is to save the whole tilebag. It would be nice to have
an integer that I could use to re-create the same game. I was working in
some kind of hash function. I thought the rand() function used the system
time or something to change each number, each time you called it. I'm a
little surprised it can be so predictable.

I think you misunderstand the primary purpose for PRNGs, the one "more
important" than games.

PRNGs are often used to generate data to test algorithms and programs,
particularly statistical, engineering, and scientific analysis
programs. It can be necessary to compare such programs by having them
process exactly the data sequence. If it were not possible to
recreate a specific sequence from a PRNG whenever needed, people doing
this sort of work would need to generate large files of data sequences
just so they could feed them into different programs.

A 16bit number would be OK, but maybe I should string a couple of rand()
generated numbers together.

Has anyone played with bitshifting and XOR'ing several rands to make them
more random, or perhaps XOR with the current time/date?

Something like put a rand() (15bit) into a 64bit number, shift a random
amount (<64bit), XOR or even "&" with another rand, loop again "X" times...

Just wondering if this has been tried, and whether this makes the number
more or less random....

<sigh>

There is an enormous amount of information about PRNGs available on
the web, try a Google search. But in general, trying to make the
results from a PRNG "more random" are much more likely to make the
less so.

If you want 32-bit pseudo random numbers, you can find source code for
many of them on the web. That also frees you from dependence on any
particular compiler's implementation of rand().

 

[Keith Thompson]

'rand' has to be predictable; otherwise, how could you ever test it
for correctness?

Well, you could perform statistical tests. In fact, a good test of
rand() should both verify that it generates a consistent sequence for
a given seed, and that each sequence meets certain statistical
criteria (though failing the latter doesn't necessarily imply
non-compliance).

srand((unsigned)time(0)) is the "canonical" way to get a random seed
into the PRNG. Of course it's not secure, but it's good enough for
games and things that you won't ever need to run twice in close succession
expecting different outputs.

That's assuming that the value returned by time(0), cast to unsigned,
varies significantly over a reasonable period of time. If time()
returns a double representing the number of days since some epoch, the
value of (unsigned)time(0) will only change once per day. I know of
no such implementation, but you might as well avoid non-portable
assumptions if you can.

 

[Arthur J. O'Dwyer]

Well, you could perform statistical tests. In fact, a good test of
rand() should both verify that it generates a consistent sequence for
a given seed, and that each sequence meets certain statistical
criteria (though failing the latter doesn't necessarily imply
non-compliance).

But if it weren't repeatable, your results wouldn't be reproducible...
Okay, it's possible. I just think it would be harder to prove
the correctness of a real RNG (under all possible conditions) than of
a PRNG (under ditto). For one thing, you'd have to do that statistical
proof (*not* test; tests don't prove anything, least of all correctness
on whatever the *source* of true randomness was, and that would be
*really* tricky, I think.
expecting different outputs.[*]

That's assuming that the value returned by time(0), cast to unsigned,
varies significantly over a reasonable period of time. If time()
returns a double representing the number of days since some epoch, the
value of (unsigned)time(0) will only change once per day.

[*] ...For suitable values of "in close succession."

-Arthur

 

[Nick Landsberg]

Arthur J. O'Dwyer wrote:

[SNIP]

But if it weren't repeatable, your results wouldn't be reproducible...
Okay, it's possible. I just think it would be harder to prove
the correctness of a real RNG (under all possible conditions) than of
a PRNG (under ditto). For one thing, you'd have to do that statistical
proof (*not* test; tests don't prove anything, least of all correctness
on whatever the *source* of true randomness was, and that would be
*really* tricky, I think.

Many decades ago, I remember that to check for randomness we would
use the Chi-Square test. (Google for it.) But the instructor
insisted that we run enough tests that we could also run a
Chi-Square of the Chi-Square results. The first set of
results should also follow some kind of random pattern
as determined by the second Chi-Square. Yep, that's
the tricky part of it,, I believe.

[More Snip]

 

[Viktor Lofgren]

Hi,
I want to generate a random 8 bit number using rand(0
is that possible? to expecifu the base and the lenght?
thanks

2**8 = 256. So what you would do is generate a random number
between 0 and 255. A crude way of doing it would be to call
(char)random();

Assuming that you run a x86 computer and char is 8 bits long.

 

[Keith Thompson]

2**8 = 256. So what you would do is generate a random number
between 0 and 255. A crude way of doing it would be to call
(char)random();

Assuming that you run a x86 computer and char is 8 bits long.

And that char is unsigned, among other assumptions.

The idea was proposed and shot down elsewhere in this thread.

Oddly enough, question 13.16 in the C FAQ is "How can I get random
integers in a certain range?".

<http://www.eskimo.com/~scs/C-faq/top.html>

 

[Orhan Kavrakoglu]

[snip]

I am interested in this as well. I have a game that fills a bag with tiles
(or it could be a deck of cards, whatever) and I would like to just store a
(32-bit?) number that would re-generate the exact same sequence. It would
limit game to have 4billion possible beginnings, but that might just be
enough. ;-)

The game has 4 billion possible beginnings anyway. I mean, as long as
you're not changing seed values with srand(), your rand()s will
produce only 4 billion different sets of numbers.

Here's a simple pseudo-random number generator in pseudo-code:

number[t] = (M * number[t-1]) % N

number[0] is the seed, and for best results, M and N are prime
numbers. (I'm sure there are other factors as well, but I can't list
them off the top of my head.)

For a C implementation using the method above, I'd say that M is a 10
or 9-digit prime number, and N is 32767, which looks like a Mersenne
prime, but is unfortunetely not.

 

[Michael Wojcik]

[using PRNG for a game]

There's some good material in the sci.crypt FAQ on using a PRNG to
shuffle a deck of cards. I recommend looking at that.

 

[Michael Wojcik]

srand((unsigned)time(0)) is the "canonical" way to get a random seed
into the PRNG. Of course it's not secure, but it's good enough for
games and things that you won't ever need to run twice in close succession
expecting different outputs.

For sufficently small values of "good enough", perhaps. Games that
use srand((unsigned)time(0)), or for that matter the rand() provided
by many implementations, often have terrible randomizing (shuffling
or what have you). Take card games played with a full deck, for
example - you don't get lg(52!) bits of entropy in your typical
rand() implementation, and srand() certainly doesn't let you set
them. (And many people use lousy shuffling algorithms.)

C simply doesn't provide a good PRNG for most games as part of the
standard library. People who want to write games with a (pseudo-)
random aspect in C should do a bit of research and find out how to
do it correctly.

 

[Michael Wojcik]

Many decades ago, I remember that to check for randomness we would
use the Chi-Square test. (Google for it.) But the instructor
insisted that we run enough tests that we could also run a
Chi-Square of the Chi-Square results. The first set of
results should also follow some kind of random pattern
as determined by the second Chi-Square. Yep, that's
the tricky part of it,, I believe.

There's a lot of literature on PRNG quality tests. Knuth goes into
it in some detail, IIRC. George Marsaglia (who occasionally posts
here) maintains the popular Diehard suite of tests for RNGs and PRNGs
(or more precisely, for sequences of values purported to be random or
pseudorandom). You can read about Diehard's tests at [1].

They include tests for value spacings, run lengths, missing values
under various encodings, and so forth.

1. http://stat.fsu.edu/pub/diehard/cdrom/source/tests.txt

 

[Nick Landsberg]

Many decades ago, I remember that to check for randomness we would
use the Chi-Square test. (Google for it.) But the instructor
insisted that we run enough tests that we could also run a
Chi-Square of the Chi-Square results. The first set of
results should also follow some kind of random pattern
as determined by the second Chi-Square. Yep, that's
the tricky part of it,, I believe.

There's a lot of literature on PRNG quality tests. Knuth goes into
it in some detail, IIRC. George Marsaglia (who occasionally posts
here) maintains the popular Diehard suite of tests for RNGs and PRNGs
(or more precisely, for sequences of values purported to be random or
pseudorandom). You can read about Diehard's tests at [1].

They include tests for value spacings, run lengths, missing values
under various encodings, and so forth.

1. http://stat.fsu.edu/pub/diehard/cdrom/source/tests.txt

That was fascinating reading.
Thanks for the reference.

 

[Keith Thompson]

The game has 4 billion possible beginnings anyway. I mean, as long as
you're not changing seed values with srand(), your rand()s will
produce only 4 billion different sets of numbers.

That's assuming that unsigned int (the type of the argument to
srand()) is 32 bits, and that srand() uses all 32 bits.

 

[CBFalconer]

.... snip ...

There's a lot of literature on PRNG quality tests. Knuth goes into
it in some detail, IIRC. George Marsaglia (who occasionally posts
here) maintains the popular Diehard suite of tests for RNGs and PRNGs
(or more precisely, for sequences of values purported to be random or
pseudorandom). You can read about Diehard's tests at [1].

They include tests for value spacings, run lengths, missing values
under various encodings, and so forth.

1. http://stat.fsu.edu/pub/diehard/cdrom/source/tests.txt

Accessing that results in "Forbidden".

 

[August Derleth]

Accessing that results in "Forbidden".

I got it just fine. Should I email it to you?

 

[CBFalconer]

I got it just fine. Should I email it to you?

That would be pleasant, thanks. At worldnet.att.net.

 

[Michael Wojcik]

Accessing that results in "Forbidden".

Interesting. I retrieved it fine with IE, but after I saw your
post I did a quick manual test (piped the GET request into a simple
TCP client, similar to netcat), and did indeed get an HTTP 403
(Forbidden) error.

http://stat.fsu.edu/pub/diehard/cdrom/ is OK, but source/ or anything
under it returns a 403. I'm not sure what IE is doing under the
covers. Ah - a bit of conversation snooping and further experimenta-
tion have provided the answer. The server at stat.fsu.edu will only
serve the document in response to an HTTP/1.1 request, not an
HTTP/1.0 request. (It has to be a well-formed HTTP/1.1 request, with
a Host header as well as the Request-line.)

HTTP/1.1 really is an improvement over HTTP/1.0 in many respects, and
all other things being equal it would be good to use a browser that
supports it. But all other things are not, of course, equal, and I
understand why some people are reluctant to move to a newer browser.
(I have to use IE for work reasons, but I'm not happy with it.)

--
Michael Wojcik (e-mail address removed)

An intense imaginative activity accompanied by a psychological and moral
passivity is bound eventually to result in a curbing of the growth to
maturity and in consequent artistic repetitiveness and stultification.
-- D. S. Savage