Way for computing random primes in standard C.

[Keith Thompson]

False.

What you are claiming is that the randomness of the sequence increases as
the rand() function is used.

No, nobody made that claim.

[snip]

By calling srand() we increased the probability of
some numbers which had low probability and reduced the probability of other
numbers which had low probability.

So you're asserting that repeatedly calling srand() improves the
randomness of the numbers returned by rand()? In particular, you're
claming that that something like this:

int rand_array[SOME_SIZE];
int index = 0;
srand(some_value);
rand_array[index++] = rand();
rand_array[index++] = rand();
rand_array[index++] = rand();
srand(some_other_value);
rand_array[index++] = rand();
rand_array[index++] = rand();
rand_array[index++] = rand();

is likely to yield better (more random) results than if the second
call to srand() were removed (perhaps with a different number of
calls)?

If this is correct, then there's an error in the comp.lang.c FAQ,
question 13.17. If you can convince Steve Summit that this is an
error, I'm sure he'll be willing to change it. You'll need to support
your claim with concrete evidence, of course. It would also be
interesting to know how often, under what circumstances, and with what
arguments srand() should be called to get the best possible
pseudo-random numbers. (I happen to think that you're completely
wrong, but I've been mistaken before.)

If I've misunderstand what you're claiming, please clarify.

 

[CBFalconer]

.... snip ...

So you're asserting that repeatedly calling srand() improves the
randomness of the numbers returned by rand()? In particular, you're
claming that that something like this:

int rand_array[SOME_SIZE];
int index = 0;
srand(some_value);
rand_array[index++] = rand();
rand_array[index++] = rand();
rand_array[index++] = rand();
srand(some_other_value);
rand_array[index++] = rand();
rand_array[index++] = rand();
rand_array[index++] = rand();

is likely to yield better (more random) results than if the second
call to srand() were removed (perhaps with a different number of
calls)?

If this is correct, then there's an error in the comp.lang.c FAQ,
question 13.17. If you can convince Steve Summit that this is an
error, I'm sure he'll be willing to change it. You'll need to support
your claim with concrete evidence, of course. It would also be
interesting to know how often, under what circumstances, and with what
arguments srand() should be called to get the best possible
pseudo-random numbers. (I happen to think that you're completely
wrong, but I've been mistaken before.)

It could happen with particularly bad random number generators.
For example, some algorithms can get into multiple independant
cycles, of different lengths. However even Microsoft is not likely
to use these algorithms.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

 

[Keith Thompson]

Keith Thompson wrote: [snip]
It could happen with particularly bad random number generators.
For example, some algorithms can get into multiple independant
cycles, of different lengths. However even Microsoft is not likely
to use these algorithms.

As far as I know the sample implementation in the standard doesn't
have that flaw, and there's no excuse for using an implementation
worse than that.

 

[Ben Bacarisse]

By calling srand() we increased the
probability of
some numbers which had low probability and reduced the probability of
other numbers which had low probability.

So you're asserting that repeatedly calling srand() improves the
randomness of the numbers returned by rand()? In particular, you're
claming that that something like this:

int rand_array[SOME_SIZE];
int index = 0;
srand(some_value);
rand_array[index++] = rand();
rand_array[index++] = rand();
rand_array[index++] = rand();
srand(some_other_value);
rand_array[index++] = rand();
rand_array[index++] = rand();
rand_array[index++] = rand();

is likely to yield better (more random) results than if the second call to
srand() were removed (perhaps with a different number of calls)?

There is a degenerate case where you will almost certainly get better
"randomness": by calling srand with a seed chosen by a high-quality
hardware RNG before every call to rand. (I say almost because the
transformation from srand to the result of rand just *might* be
pathologically bad.)

Obviously, this case is absurd (just use your better source) but it is
possible (I'll put it no more strongly than that) that in cases where the
entropy of your source is precious you might get some improvement by
calling srand with a new random seed for every nth call to rand (for n >
1). If we use n==0 for the case where we use our source directly, then
we have a continuity from n==0 giving good randomness but using up our
precious entropy, to n==inf where we use none of it and rely on rand
entirely. The optimal point (if there is one) will depend on
circumstances.

However (and it is a big however) as someone who has worked on RNGs for
cryptographic applications I would not recommend this technique at all!
The reason is that the effort involved in studying the algorithm used by
srand/rand to ensure that is does not introduce any serious flaws in the
random number stream is just too great. If you need a very high quality
stream, there are plenty of open source implementations available (with
supporting analysis). If you don't them using rand (with srand called
once at the start) will do just fine. Interleaving calls to srand will
cause the reader to wonder if you have made things mysteriously worse,
even though it might well be helping a little.

In short, I agree with you that it is a Bad Idea.

 

[Kenneth Brody]

By calling srand() we increased the probability of
some numbers which had low probability and reduced the probability of other
numbers which had low probability.

So you're asserting that repeatedly calling srand() improves the
randomness of the numbers returned by rand()? In particular, you're
claming that that something like this:

int rand_array[SOME_SIZE];
int index = 0;
srand(some_value);
rand_array[index++] = rand(); [...]
srand(some_other_value);
rand_array[index++] = rand(); [...]

is likely to yield better (more random) results than if the second
call to srand() were removed (perhaps with a different number of
calls)?

[...]

I know someone who did (in a language other than C) the equivalent of:

int MyRandomNumber(void)
{
int ret;
srand(ret = rand());
return(ret);
}

(ie: constantly re-seeding the generator with the previous return value)
and then complained about the low-randomness.

--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:[email protected]>

 

[Rod Pemberton]

That is not what I am claiming at all. You are misreading my post as
well as Keith's.
Fine...


Of course it is. But if the algorithm is hosed, how can calling srand
multiple times help?

The algorithm isn't "hosed." It's just not a random number generator. It's
pseudo-random.

You have introduced a chicken-and-egg problem here: To get appropriately
random numbers, you are claiming, one needs to keep reseeding the random
number generator with appropriately random numbers. Huh?

If I was misreading before, you are now. As I've stated previously, the
randomness is in the non-perfect algorithm in rand(). But, the set of
numbers generated by rand() is affected by srand(). srand() doesn't affect
the randomness of values that rand() generates, it only changes the set of
generated numbers. Since the algorithm isn't a perfect-random number
generator but a pseudo-random number generator, the probabilities of certain
numbers occurring is higher than others. These probabilities can be shifted
by calls to srand().


Rod Pemberton

 

[Rod Pemberton]

False.

What you are claiming is that the randomness of the sequence increases as
the rand() function is used.

No, nobody made that claim.

[snip]

By calling srand() we increased the probability of
some numbers which had low probability and reduced the probability of other
numbers which had low probability.

So you're asserting that repeatedly calling srand() improves the
randomness of the numbers returned by rand()? In particular, you're
claming that that something like this:

is likely to yield better (more random) results than if the second
call to srand() were removed (perhaps with a different number of
calls)?

KEITH: NO! Completely incorrect! This is the fifth time and last time.
Since I'm tied of trying to get through to you, I'll just repeat what I
posted to Sinaur. If you don't comprehend, you can deal with your
inabilities in private.

"As I've stated previously, the randomness is in the non-perfect algorithm
in rand(). But, the set of numbers generated by rand() is affected by
srand(). srand() doesn't affect the randomness of values that rand()
generates, it only changes the set of generated numbers. Since the
algorithm isn't a perfect-random number generator but a pseudo-random number
generator, the probabilities of certain numbers occurring is higher than
others. These probabilities can be shifted by calls to srand(). "


Rod Pemberton

 

[Keith Thompson]

KEITH: NO! Completely incorrect! This is the fifth time and last time.
Since I'm tied of trying to get through to you, I'll just repeat what I
posted to Sinaur. If you don't comprehend, you can deal with your
inabilities in private.

"As I've stated previously, the randomness is in the non-perfect algorithm
in rand(). But, the set of numbers generated by rand() is affected by
srand(). srand() doesn't affect the randomness of values that rand()
generates, it only changes the set of generated numbers. Since the
algorithm isn't a perfect-random number generator but a pseudo-random number
generator, the probabilities of certain numbers occurring is higher than
others. These probabilities can be shifted by calls to srand(). "

The fact that rand() is a pseudo-random number generator does not
imply that certain numbers appear with a higher probability than
others. For example, if RAND_MAX==32767, it's entirely possible that
each of the 32768 possible values will appear with exactly equal
probability over the long run, for each possible seed. (The generator
can still be imperfectly random even if this is true. For example,
rand() is likely to repeat over a cycle whose length depends on the
size of its internal state; a true random number generator would not
do so, though over the very long run it will sometimes appear to do
so.)

Or have I misunderstood what you meant by "the probabilities of
certain numbers occurring is higher than others"?

In your initial contribution to this thread, you wrote:

] The algorithm which generates a semi-random or pseudo-random number
] sequence has some internal initial values. If you don't call
] srand(), the sequence will be semi-random but will be the same
] sequence every time you run your program. So, if you were to write
] a card playing program, you might call srand() at every shuffle to
] start a new semi-random sequence and call rand() to generate the
] deck of cards. The "randomness" comes from the algorithm in rand()
] not from the starting values in generated by srand().

My response was that it would make more sense to call, say,
srand(time(NULL)) exactly once at program startup, and use successive
values from the *same* pseudo-random sequence for successive shuffles.
You said I was wrong.

You seem to be claiming that calling srand() *again* for each shuffle
is somehow better than calling srand() exactly once at program startup
and generating all shuffles from the single resulting pseudo-random
sequence. (By "calling srand()", I mean "calling the srand function
with some appropriate argument, such as srand(time(NULL))".) Is that
in fact what you've been claiming? In what sense is calling srand()
repeatedly better than calling it only once? How is starting a new
pseudo-random sequence better than continuing to use the original one?

Note that inserting an extra call to rand() will also change the
behavior of subsequent calls to rand(); would that suit your purpose
as well?

 

[A. Sinan Unur]

...
Calling srand() more than once
makes sense *only* if you want to repeat the same sequence.

False.

You apparently meant to say this: "'Calling srand() more than
once' _with_the_same_value_ 'makes sense *only* if you want to
repeat the same sequence.'"

You are misreading Keith's post. Calling srand multiple times with
different seeds during the life time of the program *decreases*
the randomness of the sequence generated.

False.

What you are claiming is that the randomness of the sequence
increases as the rand() function is used.

No, nobody made that claim.

[snip]

By calling srand() we increased the probability of
some numbers which had low probability and reduced the probability
of other numbers which had low probability.

This is nonsense.

KEITH: NO! Completely incorrect! This is the fifth time and last
time. Since I'm tied of trying to get through to you, I'll just repeat
what I posted to Sinaur.

The correct spelling of my name is 'Sinan'.

If you don't comprehend, you can deal with your inabilities in
private.

It is impossible for me to comprehend what you are saying because it
makes no sense. There are a number of standard texts on pseudo RNGs. I
suggest you look them up, and try to find one that recommends constant
reseeding as a way of improving 'randomness'.

"As I've stated previously, the randomness is in the non-perfect
algorithm in rand().

There is no 'the' algorithm in rand(). There are many different
algorithms, and even the simplest ones may differ in the choice of
parameters.

But, the set of numbers generated by rand() is
affected by srand(). srand() doesn't affect the randomness of values
that rand() generates, it only changes the set of generated numbers.
Since the algorithm isn't a perfect-random number generator but a
pseudo-random number generator, the probabilities of certain numbers
occurring is higher than others. These probabilities can be shifted
by calls to srand(). "

But not, in general, in a way that makes the resulting sequence exhibit
desirable properties such as lack of autocorrelation or other patterns.
Consider the simple example:

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

void re_seed(int seed) {
#ifdef HOSE_ME
srand(seed);
#endif
}

int main(int argc, char *argv[]) {
int i, count;
if ( argc == 1 ) {
count = 1000;
} else {
count = atoi(argv[1]);
}
srand(time(NULL));

for ( i = 0; i < count; ++i ) {
int ri = rand();
re_seed(ri);
printf("%d\n", ri);
}

return 0;
}

/*EOF*/

Compile this program, examine generated sequences. I generated 10
sequences of 100 numbers with HOSE_ME defined, and 10 without.

Then I tested each sequence for autocorrelation. Every sequence with
HOSE_ME defined showed statistically significant autocorrelation at
alpha = 5% where none of the sequences without HOSE_ME defined did.

This is, of course, not a proof, but an example of what we are trying to
get across to you. Both versions of the program were compiled with both
gcc version 3.4.4 and Microsoft (R) 32-bit C/C++ Optimizing Compiler
Version 13.10.3077 for 80x86.

Sinan

 

[mensanator]

...
Calling srand() more than once
makes sense *only* if you want to repeat the same sequence.

False.

You apparently meant to say this: "'Calling srand() more than once'
_with_the_same_value_ 'makes sense *only* if you want to repeat the
same sequence.'"

You are misreading Keith's post. Calling srand multiple times with
different seeds during the life time of the program *decreases* the
randomness of the sequence generated.

False.

What you are claiming is that the randomness of the sequence increases as
the rand() function is used.

No, nobody made that claim.

[snip]

By calling srand() we increased the probability of
some numbers which had low probability and reduced the probability of other
numbers which had low probability.

So you're asserting that repeatedly calling srand() improves the
randomness of the numbers returned by rand()? In particular, you're
claming that that something like this:

is likely to yield better (more random) results than if the second
call to srand() were removed (perhaps with a different number of
calls)?

KEITH: NO! Completely incorrect! This is the fifth time and last time.
Since I'm tied of trying to get through to you, I'll just repeat what I
posted to Sinaur. If you don't comprehend, you can deal with your
inabilities in private.

"As I've stated previously, the randomness is in the non-perfect algorithm
in rand(). But, the set of numbers generated by rand() is affected by
srand().

No, it's not. There is only ONE sequence.

srand() doesn't affect the randomness of values that rand()
generates, it only changes the set of generated numbers.

It does not, as there is only ONE sequence. What srand() does
is change your position in the sequence.

Since the
algorithm isn't a perfect-random number generator but a pseudo-random number
generator, the probabilities of certain numbers occurring is higher than
others. These probabilities can be shifted by calls to srand(). "

No, they can't. If, starting at state 123456, and you have the
sequence

123456: 123345
123457: 011775
123458: 394875

then that sequence of numbers ALWAYS appears in that order
anytime the sequence finds itself at state 123456. If you start at
state 123456 and generate 1000 PRNs and you then call srand(),
there is a non-zero probability that the state will be set to some
number less than 123456. If it were, say 100 less, then your next
run of 1000 numbers would have a sequence that duplicates the
last 900 numbers of the first block of 1000.

Explain how this is "more random".

 

[websnarf]

Is there a function in the standard C library which returns a prime
number which is also pseudo-random?

No. The ANSI C standard doesn't have that sort of content in it.

Assuming there isn't, as it appears from the docs that I have, is there
a better way than to fill an array of range 0... RAND_MAX with
pre-computed primes and using the output of rand() to index into it to
extract a random prime.

You can use the primeAt() function here:

http://www.pobox.com/~qed/primeat.zip

indexed by a pseudo random number. This will give exactly even
probabilities for all the primes that are at most 32 bits.

Now, of course you may need a range larger than 0 ... RAND_MAX. You
can build that from code found here:

http://www.pobox.com/~qed/random.html

Also what is meant by reinitialising the rand() function with srand(1)?
Does it mean that further calls to rand() will return numbers with a new
starting point? If so, how is it different to calling srand() with a
seed value such as that returned by the time() function?

rand() outputs numbers in a deterministic sequence indexed by the seed
passed to srand(). Calling srand(time(NULL)) makes the sequence change
over time (usually different for every second of time.)

Thank you all for the help. I find this group very useful.

(That is so ironic ...)

 

[Micah Cowan]

In your initial contribution to this thread, you wrote:

(Rod Pemberton wrote

] The algorithm which generates a semi-random or pseudo-random number
] sequence has some internal initial values. If you don't call
] srand(), the sequence will be semi-random but will be the same
] sequence every time you run your program. So, if you were to write
] a card playing program, you might call srand() at every shuffle to
] start a new semi-random sequence and call rand() to generate the
] deck of cards. The "randomness" comes from the algorithm in rand()
] not from the starting values in generated by srand().

My response was that it would make more sense to call, say,
srand(time(NULL)) exactly once at program startup, and use successive
values from the *same* pseudo-random sequence for successive shuffles.
You said I was wrong.

You seem to be claiming that calling srand() *again* for each shuffle
is somehow better than calling srand() exactly once at program startup
and generating all shuffles from the single resulting pseudo-random
sequence. (By "calling srand()", I mean "calling the srand function
with some appropriate argument, such as srand(time(NULL))".) Is that
in fact what you've been claiming? In what sense is calling srand()
repeatedly better than calling it only once? How is starting a new
pseudo-random sequence better than continuing to use the original one?

Rod is probably referring to the fact that any PRNG is going to be
periodic in output. I think his point is that it makes sense to switch
to a new "sequence" by re-seeding, before the period expires.

Note that he doesn't say you should call srand() before every call to
rand(), he says you should call it once per shuffle. That's probably
once for every 52 calls to rand(). And those 52 calls will happen
quickly, in succession, but then there's likely to be a fairly long
lag 'til the next rand() call (before which he proposes to reseed).

This might not necessarily be a bad idea, and might even improve
randomness provided the time taken for each game varies.

However, for the vast majority of other types applications, it is
likely to be a bad idea, since the time between calls to srand() may
be too predictable; and of course, if srand() is called too
frequently, the results probably won't be very random, since the
initial seeds to srand() are likely to be very similar to eachother.

To my mind, srand() every 52 times is still too frequent, considering
that a typical PRNG is likely to have a period of far greater than
52. Now, if you called srand() every 500 shuffles (assuming a fairly dumb
PRNG), then you might actually improve the randomness. This requires
that there's at least been enough time passed to change the seed (if
you're using time()), and is much more likely to improve randomness if
the periods of time between srand()s vary, themselves.

Still, I don't know that calling srand() every shuffle will hurt,
either (again, given varying times in game lengths): it probably
depends on the algorithm used by the PRNG.

I think typical implementations of rand() have long enough periods
that it still doesn't make much sense to do this. Several
implementations have periods of 2**32, in which case you'll never hit
the limit, no matter how many card games you play in your lifetime.

However, in the end, his suggestion of calling srand() for every
shuffle is no different from calling srand() only once, in a version
of the game that only allows you to play one hand.

-Micah

 

[Nelu]

You seem to be claiming that calling srand() *again* for each shuffle
is somehow better than calling srand() exactly once at program startup
and generating all shuffles from the single resulting pseudo-random
sequence. (By "calling srand()", I mean "calling the srand function
with some appropriate argument, such as srand(time(NULL))".) Is that
in fact what you've been claiming? In what sense is calling srand()
repeatedly better than calling it only once? How is starting a new
pseudo-random sequence better than continuing to use the original one?

I'm not into RNGs so I may be wrong about this, but I think Rod's right
in a way. The sequence of numbers generated by the RNG is always the
same for a given seed. Calling seed repeatedly, using a predefined
algorithm can build a new RNGs on top of the existing one. As long as
the sequence of calls to seed can be kept secret no one should,
theoretically, be able to repeat your sequence. That's mixing known RNG
algorithm with an unknown algorithm of reseeding. I think this is the
end of him being right.
However, leaving aside the fact that it's unlikely to keep the sequence
a secret from a good hacker there are two problems:
1. Calling seed every time, before calling rand, is not a good way to
reseed as it is highly predictable. No matter how reseeding is done
using the RNG, it is repeatable in the same conditions so it's by no
means better than the default RNG for simulations.
2. This is never going to be a good enough algorithm to use in
encryptions, partly because of the hacker and partly because of point
1.
So, what you can get is just another that whose sequence is repeatable
if you know the reseeding pattern. That's in no way better than using
the default RNG and seeding it once.

 

[Nelu]

No, it's not. There is only ONE sequence.

Not entirely sure about this. It depends on how the RNG generates the
numbers and I'm not sure that the standard says the algorithm has to be
a specific one. If it generates numbers based on previously generated
numbers you may be wrong.

 

[mensanator]

Not entirely sure about this. It depends on how the RNG generates the
numbers and I'm not sure that the standard says the algorithm has to be
a specific one. If it generates numbers based on previously generated
numbers you may be wrong.

If I'm wrong, then calling srand() with a constant would not
give you the same sequence, would it?

 

[Keith Thompson]

Rod Pemberton wrote: [...]

"As I've stated previously, the randomness is in the non-perfect algorithm
in rand(). But, the set of numbers generated by rand() is affected by
srand().

No, it's not. There is only ONE sequence.

srand() doesn't affect the randomness of values that rand()
generates, it only changes the set of generated numbers.

It does not, as there is only ONE sequence. What srand() does
is change your position in the sequence.

No, that's not correct.

C99 7.20.2.2p2 says:

The srand function uses the argument as a seed for a new sequence
of pseudo-random numbers to be returned by subsequent calls to
rand. If srand is then called with the same seed value, the
sequence of pseudo-random numbers shall be repeated. If rand is
called before any calls to srand have been made, the same sequence
shall be generated as when srand is first called with a seed value
of 1.

Note the phrase "a new sequence". It's possible, but not required,
that the "new sequence" matches some other sequence at a different
position. It's also possible that it doesn't. For example, there may
be no overlap between the sequence created by srand(1) and the one
created by srand(2) (this is particularly likely if rand()'s internal
state has more bits than the unsigned int argument to srand()).

(This doesn't support Rod Pemberton's claims, of course. Calling
srand() a second time will give you a different sequence; there's no
reason to think it's a better sequence.)

 

[Nelu]

You seem to be claiming that calling srand() *again* for each shuffle
is somehow better than calling srand() exactly once at program startup
and generating all shuffles from the single resulting pseudo-random
sequence. (By "calling srand()", I mean "calling the srand function
with some appropriate argument, such as srand(time(NULL))".) Is that
in fact what you've been claiming? In what sense is calling srand()
repeatedly better than calling it only once? How is starting a new
pseudo-random sequence better than continuing to use the original one?

I'm not into RNGs so I may be wrong about this, but I think Rod's right
in a way. The sequence of numbers generated by the RNG is always the
same for a given seed. Calling seed repeatedly, using a predefined
algorithm can build a new RNGs on top of the existing one. As long as
the sequence of calls to seed can be kept secret no one should,
theoretically, be able to repeat your sequence. That's mixing known RNG
algorithm with an unknown algorithm of reseeding. I think this is the
end of him being right.
However, leaving aside the fact that it's unlikely to keep the sequence
a secret from a good hacker there are two problems:
1. Calling seed every time, before calling rand, is not a good way to
reseed as it is highly predictable. No matter how reseeding is done
using the RNG, it is repeatable in the same conditions so it's by no
means better than the default RNG for simulations.
2. This is never going to be a good enough algorithm to use in
encryptions, partly because of the hacker and partly because of point
1.
So, what you can get is just another that whose sequence is repeatable
if you know the reseeding pattern. That's in no way better than using
the default RNG and seeding it once.

 

[websnarf]

False.

Right -- but your response is not correct either.

You apparently meant to say this: "'Calling srand() more than once'
_with_the_same_value_ 'makes sense *only* if you want to repeat the same
sequence.'" But, you didn't say that. Calling srand() with time(NULL) at a
later point in time, i.e. different value, will generate a new starting
point for rand() and therefore different pseudo-random sequence. Do you
want me to post code and data that demonstrate this?

Calling srand (time (NULL)) multiple times in a program will usually
*not* introduce more entropy. Especially not if you do that with a
frequency >= once per second. Also calling srand is usually not
necessary at a frequency >= the state size of rand (though for most C
language implementations, the state size is tiny -- usually 32 bits.)

Calling srand (entropy (eindx++)) makes sense so long as you come up
with a new source of entropy with each call. What this means is that
the value of entropy (x) and entropy (x+1) should have a significant
amount of independence from each other. This is valuable if you are
worried that someone might try to reverse engineer your random number
seed by observing a long enough sequence of the output.

The problem is that getting independent sources of entropy usually
involves getting your hands dirty. time (NULL) and getpid () are two
common sources, but that's only 64 bits worth. Other common practical
sources are things like the value of clock() in response to input
device interrupts (like keyboard or mouse inputs.) The value of
clock() during network events might also be usuable (but don't ask me
to guarantee that suggestion). Unfortunately none of this is that
useful in the context of ANSI/ISO C, which this group has made its
exclusive subject.

As one final comment -- using the ANSI C's rand() is bad because the
state size is so small -- it would require that you have access to a
source of entropy with basically every single call. With PRNGs like
the Mersenne Twister, or Marsaglia's CMWC you only need one source of
entropy per 600 or 1000 calls to the PRNG.

You can read more about this (and more deeper ideas) by looking for the
Yarrow RNG method by Schneier et al.

 

[Keith Thompson]

I'm not into RNGs so I may be wrong about this, but I think Rod's right
in a way. The sequence of numbers generated by the RNG is always the
same for a given seed. Calling seed repeatedly, using a predefined
algorithm can build a new RNGs on top of the existing one. As long as
the sequence of calls to seed can be kept secret no one should,
theoretically, be able to repeat your sequence. That's mixing known RNG
algorithm with an unknown algorithm of reseeding. I think this is the
end of him being right.

I'm no expert on RNGs either, but my understanding is that piling
arbitrary stuff on top of an existing RNG is not a good approach.
It's unlikely to give you better results than just using the base RNG
directly, assuming the RNG was designed at all competently in the
first place. A given RNG may not be perfect, but arbitrary minor
tweaks to it will probably make it worse. (I think Knuth writes about
this.)

If your RNG is good enough, just use it. If it's not good enough, use
something else.

However, leaving aside the fact that it's unlikely to keep the sequence
a secret from a good hacker there are two problems:

If you want to keep the sequence secret (for cryptography, for
example), *don't* use rand(). srand() and rand() are specifically
designed to produce *repeatable* sequences. (And if you want reliable
advice, ask someone who knows more about this stuff than I do.)

 

[mensanator]

Rod Pemberton wrote: [...]

"As I've stated previously, the randomness is in the non-perfect algorithm
in rand(). But, the set of numbers generated by rand() is affected by
srand().

No, it's not. There is only ONE sequence.

srand() doesn't affect the randomness of values that rand()
generates, it only changes the set of generated numbers.

It does not, as there is only ONE sequence. What srand() does
is change your position in the sequence.

No, that's not correct.

C99 7.20.2.2p2 says:

The srand function uses the argument as a seed for a new sequence
of pseudo-random numbers to be returned by subsequent calls to
rand. If srand is then called with the same seed value, the
sequence of pseudo-random numbers shall be repeated. If rand is
called before any calls to srand have been made, the same sequence
shall be generated as when srand is first called with a seed value
of 1.

Note the phrase "a new sequence". It's possible, but not required,
that the "new sequence" matches some other sequence at a different
position. It's also possible that it doesn't. For example, there may
be no overlap between the sequence created by srand(1) and the one
created by srand(2) (this is particularly likely if rand()'s internal
state has more bits than the unsigned int argument to srand()).

When it's stated that
"...the Mersenne Twister as the core generator.
It produces 53-bit precision floats and has a period of 2**19937-1."

Doesn't it mean that there are 2**19937-1 states and if one were
to actually call it 2**19937 times, then one would be right back
where one started regardless of what number srand() was called with?

I was not implying that srand(1) and srand(2) have adjacent states.
But doesn't periodic mean that at whatever state # srand(1) starts in,
it must eventually reach the same state that srand(2) starts in?

So IF the PRNG is periodic AND the same seed gives the same
sequence THEN sequences generated by diffrent srand() calls
must overlap. If wrong, why?

The standard doen't imply that the PRNG must be periodic, does it?
But are there any puely mathematical ones that aren't?