473,883 Members | 2,607 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Way for computing random primes in standard C.

Hello all,

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

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.

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?

Thank you all for the help. I find this group very useful.
Feb 24 '06
104 5226
In article <du**********@c anopus.cc.umani toba.ca> ro******@ibd.nr c-cnrc.gc.ca (Walter Roberson) writes:
In article <11************ *********@t39g2 000cwt.googlegr oups.com>,
me********@aol. com <me********@aol .com> wrote:
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?


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, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Mar 1 '06 #61
In article <ln************ @nuthaus.mib.or g> Keith Thompson <ks***@mib.or g> writes:
....
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.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Mar 1 '06 #62
In article <Iv********@cwi .nl>, Dik T. Winter <Di********@cwi .nl> wrote:
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.
--
There are some ideas so wrong that only a very intelligent person
could believe in them. -- George Orwell
Mar 1 '06 #63
me********@aol. com wrote:
Walter Roberson wrote:
me********@aol. com <me********@aol .com> wrote:
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?


Not necessarily.


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.
It would be possible to the initial seed to affect parameters
in the PRNG, such that srand(1) and srand(2) each had the same
period, but that the cyles for the two were not the same.


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

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

Mar 1 '06 #64
On Tue, 28 Feb 2006 17:28:10 -0800, me********@aol. com wrote:
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.

--
Ben.
Mar 1 '06 #65

<me********@aol .com> wrote in message
news:11******** **************@ e56g2000cwe.goo glegroups.com.. .

Nelu wrote:
me********@aol. com wrote:
Rod Pemberton wrote:
>
> 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.

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?


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
Mar 2 '06 #66

"A. Sinan Unur" <1u**@llenroc.u de.invalid> wrote in message
news:Xn******** *************** ****@127.0.0.1. ..
"Rod Pemberton" <do*********@so rry.bitbucket.c mm> wrote in
news:du******** ***@news3.infoa ve.net:
"Keith Thompson" <ks***@mib.or g> wrote in message
news:ln******** ****@nuthaus.mi b.org...
"Rod Pemberton" <do*********@so rry.bitbucket.c mm> writes:
> "A. Sinan Unur" <1u**@llenroc.u de.invalid> wrote in message
> news:Xn******** *************** *****@127.0.0.1 ...
>> "Rod Pemberton" <do*********@so rry.bitbucket.c mm> wrote in
>> news:dt******** ***@news3.infoa ve.net:
>> > "Keith Thompson" <ks***@mib.or g> wrote in message
>> > news:ln******** ****@nuthaus.mi b.org...
>> ...
>> >> 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.
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:

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


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...
Mar 2 '06 #67
"Rod Pemberton" <do*********@so rry.bitbucket.c mm> writes:
<me********@aol .com> wrote in message
news:11******** **************@ e56g2000cwe.goo glegroups.com.. . [...]
If I'm wrong, then calling srand() with a constant would not
give you the same sequence, would it?


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 (The_Other_Keit h) 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.
Mar 2 '06 #68
"Rod Pemberton" <do*********@so rry.bitbucket.c mm> writes:
[...]
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?

--
Keith Thompson (The_Other_Keit h) 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.
Mar 2 '06 #69

Rod Pemberton wrote:
<me********@aol .com> wrote in message
news:11******** **************@ e56g2000cwe.goo glegroups.com.. .

Nelu wrote:
me********@aol. com wrote:
> Rod Pemberton wrote:
> >
> > 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.
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?


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.

--
Ioan - Ciprian Tandau
tandau _at_ freeshell _dot_ org (hope it's not too late)
(... and that it still works...)

Mar 2 '06 #70

This thread has been closed and replies have been disabled. Please start a new discussion.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.