Way for computing random primes in standard C.

[Dik T. Winter]

> In article <[email protected]>,

>
> Not necessarily.

Indeed, it does *not* mean that there are 2**19937-1 states, there may
be more. But it *does* mean that after calling it 2**19937-1 times
you are back at the original state. It is possible that the collection
of different states is a multiple of 2**19937-1, containing different
loops, each 2**19937-1 long.

Consider the following (extremely simple) random number generator:
s = (2 * s) % 17;
It has 16 states, but a period of 8. One cycle is:
1 -> 2 -> 4 -> 8 -> 16 -> 15 -> 13 -> 9 -> 1
the other is:
3 -> 6 -> 12 -> 7 -> 14 -> 11 -> 5 -> 10 -> 3
I do not know whether that is possible with a period of 2**19937-1, but
I can not exclude it, and I think it is extremely likely that it is
possible.

....

> If we put these together, we would see that srand(1) and srand(2)
> would have the same cycles -only- if it happened the the linear
> congruential generator applied to 0x1330E16 happened to result
> in 0x2330E16 at some point.

Indeed, but a question is also, what is the period of the generator?

> Further analysis would be needed to
> see whether that ever happened -- the default multiplier and
> constant for drand48() and kin are both even, so it is not
> the usual case that "every possible n-bit value will be generated,
> eventually".

Indeed, the least significant bit will always be 0. What I am wondering
however, what does
"the low-order 16 bits of Xi are set to the arbitrary value 330E16."
mean? By any reasonable interpretation of "330E16" I come to a value
where the low order 16 bits are 0.

 

[Dik T. Winter]

> But, as you said, it's a really dumb RNG. Generally speaking, using
> only a subset of the available state for a given sequence is allowed
> by the standard, but *probably* not a good idea (unless the state is
> large enough that a subset of it gives you a very long repeating cycle
> anyway).

Given a number of possible states it can be the case that a RNG that
splits it in two (or more) cycles has better quality than a RNG that
is forced to use all states in cycle. That is one of the problems
of the standard rand. It is full cycle, but the low-order bits
display a lot of non-randomness.

 

[Walter Roberson]

What I am wondering
however, what does
"the low-order 16 bits of Xi are set to the arbitrary value 330E16."
mean? By any reasonable interpretation of "330E16" I come to a value
where the low order 16 bits are 0.

Checking the opengroup man page for drand48(), I see that it has

330E
16

which in C notation would be 0x330E .

It would appear that the other constants were similarily mangled in
the man page I was consulting: the standard multiplier is
0x5DEECE66D and the standard additive constant is 0xB or 013 (octal).
The opengroup man page uses subscripts for the bases but those
got raised on the page I was consulting so that it appears to say
B16 = 138 ... I didn't notice the complete discrepancy in magnitudes
there.

With the corrected constants, drand48() -does- alternate even
and odd, so -eventually- the state value stored for
srand(1) (0x1 << 16 | 0x330E) would get transformed into the state
value stored for srand(2) (0x2 << 16 | 0x330E) so drand48()
does turn out to be an example of a generator in which srand48(1)
and srand48(2) will produce the same cycle, just starting at
at different point in the cycle.

 

[websnarf]

Then what does "period" mean?

I think it means that each seed indexes a sequence with a period of
2**19937-1. But its not necessarily the same sequence.

Looking at the source of the Mersenne Twister, it appears to have at
most 2**19968 possible internal states. That basically means that
there are at most 2**31 disjoint sequences, if indeed MT has this
property. More likely, there is just one large cycle possible, and you
can pick one possible position with your initialization seed array. We
know that there is at least one degenerate state: the all 0s state, for
example, has a period of 1, so there are at most 2**31-1 cycles of
length 2**19937-1.

Ok, but we can't infer that from the standard, can we?

The C standard does not address the quality of random numbers.
(Resisting the urge to make the obvious generalization of this
statement ...)

 

[Ben Bacarisse]

But if all you have to go by is the standard, the issue remains:

should you call srand() more than once to "improve" the randomness?

I've been trying to justify answering no, but if those justifications
don't necessarily hold, does the answer change to yes, or does it remain
no?

The short answer is no, don't call srand more than once per program
execution. Even if you use so many calls of rand that the sequence wraps
round, the wrapped sequence will be as good as anything you can get by
re-seeding (and probably less predictable to observers as well).

Given that this is Usenet, let me qualify this. The very fact that
srand/rand is being used means that either: (a) you know that your
implementation is a good one (glibc's rand looks good to me) and calling
srand will just "get in its way" or (b) you don't have sophisticated needs
anyway so why give your program's readers something else to worry about?

The long answer requires two more pieces of information: what do you mean
by "randomness" and with what actual parameters will you call srand?

Assuming you have normal requirements for (pseudo-) randomness, an
exacting enough application to be worrying about this, and a good enough
source of entropy (sort of "real-world" randomness) you will probably have
replaced srand/rand with something more sophisticated (or examined your
implementation to see that it is OK for your needs) and you will use some
of your entropy to seed the generator at logical points in your program.
These points will not be every few calls to rand "just to help it out" but
will be when it makes sense to use your usually precious entropy for a
seed -- shuffling a multi-deck card shoe, generating a cryptographic key,
etc.

There is a special case that needs consideration -- that of programs that
do not terminate but call rand a lot since the "call srand once per
execution" advice may not be suitable for these. How often one should
call srand for such a program will vary from case to case.

 

[Rod Pemberton]

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

The function is continuous. Think of sin() and cos(). They have the exact
same appearance, but the set of numbers generated is different. If, for
example, rand() started by generating sin() instead of some other algorithm,
calling srand() will give the function a different starting point and a
different set of generated numbers, which could be cos().

Rod Pemberton

 

[Rod Pemberton]

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

I understood what you and Keith were trying to demonstrate. It seems
neither one of you understand that there is no randomness created by calling
srand(). If you had read and understood my posts, you'd know that you are
calling srand() far to frequently (in fact, you'd also need to insert a
check to wait until srand() changes). The error in your code is that you
never allow rand() to generate any psuedo-random numbers before calling
srand().

Repeating what I just posted to Nelu:
"Think of sin() and cos(). They have the exact same appearance, but the set
of numbers generated is different. If, for example, rand() started by
generating sin(), instead of some other algorithm, calling srand() will give
the function a different starting point and a different set of generated
numbers, which could be cos()."

Rod Pemberton

PS. Sorry about the error with your name, I looked at it to quickly and
dropped some letters...

 

[Keith Thompson]

The function is continuous.

I think I understand what you're saying, but the function (whatever
function you're thinking of) is *not* continuous in the usual
mathematical sense.

Think of sin() and cos(). They have the exact
same appearance, but the set of numbers generated is different. If, for
example, rand() started by generating sin() instead of some other algorithm,
calling srand() will give the function a different starting point and a
different set of generated numbers, which could be cos().

So you're assuming that rand() generates a (presumably repeating)
sequence of numbers, and srand() causes it to start at a position
within that sequence. As we've been discussing, that's possible but
not required; it's also possible that rand() could generate any of a
number of disjoint sequences, and srand() could cause it to jump from
one sequence to another.

 

[Keith Thompson]

I understood what you and Keith were trying to demonstrate. It seems
neither one of you understand that there is no randomness created by calling
srand(). If you had read and understood my posts, you'd know that you are
calling srand() far to frequently (in fact, you'd also need to insert a
check to wait until srand() changes). The error in your code is that you
never allow rand() to generate any psuedo-random numbers before calling
srand().

Remarkable.

I understand perfectly well that calling srand() does not create any
randomness. As for calling srand() too frequently, we have done so
*only* in sample programs intended to demonstrate that doing so is a
bad idea.

I have consistently advocated calling srand() once and only once in a
program, before any calls to rand().

Several days ago in this thread, I wrote:
] Calling srand() more than once makes sense *only* if you want to
] repeat the same sequence.

You disagreed (and tried to tell me that I really meant to say
something else). Have you changed your mind?

 

[Nelu]

The function is continuous. Think of sin() and cos(). They have the exact
same appearance, but the set of numbers generated is different. If, for
example, rand() started by generating sin() instead of some other algorithm,
calling srand() will give the function a different starting point and a
different set of generated numbers, which could be cos().

Rod Pemberton

Right, I've been saying that to mensanator I think. Reseeding does not
necesarily change your position in the sequence of generated data. I've
been also saying that reseeding often makes sense only if you use a RNG
to generate de reseeding sequence (wrapping a problem into a
problematic solution) or making sure that the sequence can't be found
out (keep it secret or use a better RNG to generate the seeds which is,
again, pointless, as you could use the other RNG to generate your
numbers) and that seeding once is enough.

 

[A. Sinan Unur]

The function is continuous. Think of sin() and cos(). They have the
exact same appearance, but the set of numbers generated is different.
If, for example, rand() started by generating sin() instead of some
other algorithm, calling srand() will give the function a different
starting point and a different set of generated numbers, which could
be cos().

And, the sequence generated by knowing the sequence generated by one, you
can generate the exact sequence generated by the other. If you mix the
sequences, you create a martingale:

http://en.wikipedia.org/wiki/Martingale

I don't see how that is a desirable property of a sequence generated by a
pseudo RNG.

Sinan

 

[Micah Cowan]

Remarkable.

I understand perfectly well that calling srand() does not create any
randomness. As for calling srand() too frequently, we have done so
*only* in sample programs intended to demonstrate that doing so is a
bad idea.

Yes, he seems to have completely misunderstood you. However, he never
recommended calling srand() before every rand(), as you've done in
your example code.

I have consistently advocated calling srand() once and only once in a
program, before any calls to rand().

Several days ago in this thread, I wrote:
] Calling srand() more than once makes sense *only* if you want to
] repeat the same sequence.

You disagreed (and tried to tell me that I really meant to say
something else). Have you changed your mind?

I doubt it. But his answer was at least somewhat valid, as he
advocated calling srand() every once in a while (every shuffle, or
every 52 calls to rand()), based on a fairly random interval of time
between srand()s (namely, the time it takes one to go through a deck
of cards in a card game).

-Micah

 

[Keith Thompson]

Yes, he seems to have completely misunderstood you. However, he never
recommended calling srand() before every rand(), as you've done in
your example code.

Have you confused me with someone else? I just re-examined everything
I've posted to this thread. I have never recommended calling srand()
before every rand(). (I didn't check all the articles, but I don't
think anyone else did either.) I posted a sample code snippet in
which srand() is called before every 3 calls to rand(), along with a
clear statement that it was only an example, and the number of calls
could be different. That was *not* a recommendation; I was asking Rod
Pemberton whether *he* thought that would be a good idea.

I have consistently advocated calling srand() once and only once in a
program, before any calls to rand().

Several days ago in this thread, I wrote:
] Calling srand() more than once makes sense *only* if you want to
] repeat the same sequence.

You disagreed (and tried to tell me that I really meant to say
something else). Have you changed your mind?

I doubt it. But his answer was at least somewhat valid, as he
advocated calling srand() every once in a while (every shuffle, or
every 52 calls to rand()), based on a fairly random interval of time
between srand()s (namely, the time it takes one to go through a deck
of cards in a card game).

Unless you specifically want to repeat the same sequence of
pseudo-random numbers, you should call rand() exactly once, before any
calls to rand(). If that doesn't give you good results, the solution
is to use a different pseudo-random number generator, not to call
srand() more than once. rand() is specifically designed to be
repeatable, and therefore predictable given sufficient knowledge; if
that's a problem, don't use it.

It's possible that careful re-seeding might give you better results
with some implementations of rand(), but given the availability of
free high-quality PRNGs, there's no point in bothering with that kind
of thing; any techniques you come up with won't apply to other
implementations anyway.

 

[Keith Thompson]

Unless you specifically want to repeat the same sequence of
pseudo-random numbers, you should call rand() exactly once, before any
calls to rand(). If that doesn't give you good results, the solution
is to use a different pseudo-random number generator, not to call
srand() more than once. rand() is specifically designed to be
repeatable, and therefore predictable given sufficient knowledge; if
that's a problem, don't use it.

[...]

Sorry, I meant:

Unless you specifically want to repeat the same sequence of
pseudo-random numbers, you should call *srand()* exactly once, before
any calls to rand().

 

[Pedro Graca]

[thread hijack]

Does the standard guarantee the output of this program is the same on
all implementations (that have stdlib.h)

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

int main(void) {
printf("%d\n", rand());
srand(42);
printf("%d\n", rand());
return 0;
}


On my system (I don't have a compiler for my other OS here at home)
it outputs these numbers:

1804289383
71876166

 

[Micah Cowan]

[...]
I understood what you and Keith were trying to demonstrate. It
seems neither one of you understand that there is no randomness
created by calling srand(). If you had read and understood my
posts, you'd know that you are calling srand() far to frequently
(in fact, you'd also need to insert a check to wait until srand()
changes). The error in your code is that you never allow rand()
to generate any psuedo-random numbers before calling srand().

Remarkable.

I understand perfectly well that calling srand() does not create any
randomness. As for calling srand() too frequently, we have done so
*only* in sample programs intended to demonstrate that doing so is a
bad idea.

Yes, he seems to have completely misunderstood you. However, he never
recommended calling srand() before every rand(), as you've done in
your example code.

Have you confused me with someone else? I just re-examined everything
I've posted to this thread. I have never recommended calling srand()
before every rand(). (I didn't check all the articles, but I don't
think anyone else did either.) I posted a sample code snippet in
which srand() is called before every 3 calls to rand(), along with a
clear statement that it was only an example, and the number of calls
could be different. That was *not* a recommendation; I was asking Rod
Pemberton whether *he* thought that would be a good idea.

I never said you recommended any such thing. I said that your code did
so. This is apparently wrong, as it is actually Sinan's code I'm
referring to, after checking up on it. So yes, to some degree, I'm
getting you confused.

I have consistently advocated calling srand() once and only once in a
program, before any calls to rand().

Several days ago in this thread, I wrote:
] Calling srand() more than once makes sense *only* if you want to
] repeat the same sequence.

You disagreed (and tried to tell me that I really meant to say
something else). Have you changed your mind?

I doubt it. But his answer was at least somewhat valid, as he
advocated calling srand() every once in a while (every shuffle, or
every 52 calls to rand()), based on a fairly random interval of time
between srand()s (namely, the time it takes one to go through a deck
of cards in a card game).

Unless you specifically want to repeat the same sequence of
pseudo-random numbers, you should call rand() exactly once, before any
calls to rand().

(You meant srand() instead of the first rand())

Calling srand() more than once will not repeat the same sequence of
pseudo-random numbers, unless you stupidly provide it with the same
input as the last time. I'm fairly certain Rod intended that you call
it each time with a time-based value.

If that doesn't give you good results, the solution
is to use a different pseudo-random number generator, not to call
srand() more than once.

I don't see how that follows.

 

[Micah Cowan]

[thread hijack]

Does the standard guarantee the output of this program is the same on
all implementations (that have stdlib.h)

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

int main(void) {
printf("%d\n", rand());
srand(42);
printf("%d\n", rand());
return 0;
}


On my system (I don't have a compiler for my other OS here at home)
it outputs these numbers:

1804289383
71876166

No. It is guaranteed to return the same output each time you run it on
the same implementation... but individual implementations are quite
free in their choice of what to produce.

-Micah

 

[Vladimir S. Oka]

[thread hijack]

Does the standard guarantee the output of this program is the same on
all implementations (that have stdlib.h)

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

int main(void) {
printf("%d\n", rand());
srand(42);
printf("%d\n", rand());
return 0;
}


On my system (I don't have a compiler for my other OS here at home)
it outputs these numbers:

1804289383
71876166

Same for me (SUSE Linux 10.0).

However, the Standard does not prescribe the implementation of rand()
and srand() (7.20.2.2p5). It does, however, give a portable example
implementation, but it's by no means required to be used.

 

[Al Balmer]

(You meant srand() instead of the first rand())

Calling srand() more than once will not repeat the same sequence of
pseudo-random numbers, unless you stupidly provide it with the same
input as the last time. I'm fairly certain Rod intended that you call
it each time with a time-based value.

s/stupidly/intentionally. Then consider the phrase "Unless you
specifically want to repeat the same sequence" above.

 

[Micah Cowan]

s/stupidly/intentionally.

No; srand() will repeat the same sequence of pseudo-random numbers,
whether you did it intentionally or stupidly, so I think my original
phrasing is fine.

Then consider the phrase "Unless you
specifically want to repeat the same sequence" above.

Which clearly no one on this thread /does/ want.

-Micah