Way for computing random primes in standard C.

[fieldfallow]

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.

 

[Walter Roberson]

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


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.

'better' would depend upon the density of access to the array.
If you are going to have lots of accesses then pre-computing
according to sieve or similar techniques might be best. If, though,
access is quite sparse, then it might be better to use one of
the formulas for estimating the N'th prime, and search from the
estimated value forward until you find an actual prime -- there are
well-known primality tests that can be much much faster than
doing a sequential factorization attempt.

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?

The starting point would have been reset to whatever vector is
conditioned by the seed 1.

If so, how is it different to calling srand() with a
seed value such as that returned by the time() function?

If you seed with time() then in order to repeat the sequence
you need to know what the time() was at the time of the seeding.
If you seed with a constant such as 1, then the same path will
always be followed -- and if you reseed with 1 in the same process,
then it will go back and start reusing the exact same sequence of
numbers again.

 

[Kenneth Brody]

No.

What about generating a list of N primes into an array, and then using
a PRNG to select a subscript into that array?

[...]

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

 

[Pedro Graca]

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.

I might try something like this

#include <stdlib.h>

int is_prime(int);
/* implementation left out for brevity */

int random_prime() {
int candidate = 0;

while (!is_prime(candidate)) {
candidate = rand();
}
return candidate;
}


if the fact that it is slow (probably even *very* slow) and only returns
primes up to RAND_MAX compensates the need for RAND_MAX * sizeof(prime)
bytes of memory used for the array.

 

[Micah Cowan]

What about generating a list of N primes into an array, and then using
a PRNG to select a subscript into that array?

If you'd read the OP, you'd see he's asking if there's a better way
than that: and "generating a list of N primes..." is still not a
function in the standard C library which returns a pseudo-random,
prime number.

 

[Rod Pemberton]

Hello all,

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

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.

Probably not. There are a number of algorithms for finding primes, but,
most are computationally intensive. The larger the prime the longer it will
take to compute it or prove that it is prime.

If you don't want an array, you could generate random even number from 0 to
(RAND_MAX/2). Make them all odd by adding one. Discard and generate
another odd value, if the last decimal digit ends in five, but isn't equal
to five. Then run the odd number into one of the prime number proof
algorithms. It's still computationally intensive.
Just a slight review of primes:
1) zero and one are not prime by mathematicians definitions.
2) two is the only even prime
3) five is the only odd prime whose last decimal digit is five

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?

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


Rod Pemberton

 

[Keith Thompson]

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

It would make far more sense to call srand() once at program startup.
The only reason to call srand() more than once is to reproduce the
same pseudo-random sequence.

 

[Rod Pemberton]

It would make far more sense to call srand() once at program startup.
The only reason to call srand() more than once is to reproduce the
same pseudo-random sequence.

Yes, if you call srand() without an argument, that would be the result.
And, of course, the call to srand() would be unecessary. srand() isn't
usually called without args. It's usually called with a random or changing
function like time(). It might even be considered stupid too call srand()
without args, since it could induce someone else to insert an incorrect arg.


Rod Pemberton

 

[Jordan Abel]

Probably not. There are a number of algorithms for finding primes, but,
most are computationally intensive. The larger the prime the longer it will
take to compute it or prove that it is prime.

If you don't want an array, you could generate random even number from 0 to
(RAND_MAX/2). Make them all odd by adding one. Discard and generate
another odd value, if the last decimal digit ends in five, but isn't equal
to five. Then run the odd number into one of the prime number proof
algorithms. It's still computationally intensive.
Just a slight review of primes:
1) zero and one are not prime by mathematicians definitions.
2) two is the only even prime
3) five is the only odd prime whose last decimal digit is five

This has essentially the same probabilistic characteristics as putting
the number through a naive prime number proof algorithm to begin with, (except
that divisibility by 5 is checked before 3) with the flaw that 2 will
not be yielded. The majority of non-primes will be caught quickly, and
prime numbers will have to be checked anyway.

 

[Rod Pemberton]

This has essentially the same probabilistic characteristics as putting
the number through a naive prime number proof algorithm to begin with,

It might shave a hair if he has a large array.

(except
that divisibility by 5 is checked before 3) with the flaw that 2 will
not be yielded.

Actually, neither 2 or 5 will be generated. He'd have to manually prime the
array with both them.

The majority of non-primes will be caught quickly, and
prime numbers will have to be checked anyway.

Of course, he wanted an alternative to precomputed array. I explicitly
stated that it will be computationally intensive. Although there are many
algorithms for primes and prime factorization, there are not a whole bunch
of short cuts to be taken in this area.


Rod Pemberton

 

[stathis gotsis]

If you'd read the OP, you'd see he's asking if there's a better way
than that: and "generating a list of N primes..." is still not a
function in the standard C library which returns a pseudo-random,
prime number.

Well, i believe that the OP intended to hardcode an array initialization to
some available list of primes. The first millions of primes have been
already computed, there is no need to do that again as it is time consuming.

The OP could have a large number of primes stored in a file and read up to
RAND_MAX primes into an array each time the program executes. If RAND_MAX
does not vary between program executions and is relatively small, primes can
be hardcoded in the source file. Maybe time saving can make up for space
loss.

Many primes can be found here:
http://primes.utm.edu

 

[Keith Thompson]

Yes, if you call srand() without an argument, that would be the
result. And, of course, the call to srand() would be unecessary.
srand() isn't usually called without args. It's usually called with
a random or changing function like time(). It might even be
considered stupid too call srand() without args, since it could
induce someone else to insert an incorrect arg.

You might consider reading some documentation before you post.

Calling srand() without arguments is illegal. It expects a single
argument of type unsigned int. In C90, you could call it with no
arguments if you didn't have a "#include <stdlib.h>", but that would
invoke undefined behavior.

Here's what the standard says (C99 7.20.2.2p2):

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.

Question 13.17 in the comp.lang.c FAQ also has some good information.

Calling srand(time(NULL)) exactly *once* before calling rand() is a
reasonable way to get decent random numbers (though if you want really
good random numbers you need to use something better than rand()).
Calling srand() with a constant argument gives you a reproducible
sequence of pseudo-random numbers. Calling srand() more than once
makes sense *only* if you want to repeat the same sequence.

 

[Rod Pemberton]

[...]
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().

It would make far more sense to call srand() once at program startup.
The only reason to call srand() more than once is to reproduce the
same pseudo-random sequence.

Yes, if you call srand() without an argument, that would be the
result. And, of course, the call to srand() would be unecessary.
srand() isn't usually called without args. It's usually called with
a random or changing function like time(). It might even be
considered stupid too call srand() without args, since it could
induce someone else to insert an incorrect arg.

You might consider reading some documentation before you post.

Calling srand() without arguments is illegal.

True. I stand corrected.

It expects a single
argument of type unsigned int. In C90, you could call it with no
arguments if you didn't have a "#include <stdlib.h>", but that would
invoke undefined behavior.

Why'd you recommend it? At least, thats how I took your statement...

Calling srand(time(NULL)) exactly *once* before calling rand() is a
reasonable way to get decent random numbers
True.

(though if you want really
good random numbers you need to use something better than rand()).
True.

Calling srand() with a constant argument gives you a reproducible
sequence of pseudo-random numbers.
True.

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


Rod Pemberton

 

[A. Sinan Unur]

....


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.

So, it does not make sense to call srand multiple times unless you want
to repeat the same sequence.

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?

Thanks, but no thanks. I know that you would switch to a different
sequence, I am sure Keith knows that you would switch to a different
sequence. But, it is still not the sensible thing to do.

Sinan

 

[pete]

Rod Pemberton wrote:

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.

But what's the advantage of starting a new sequence,
over just simply continuing on with the old sequence?

 

[mensanator]

But what's the advantage of starting a new sequence,
over just simply continuing on with the old sequence?

No advantage. And the "different" sequence may, in fact,
overlap the original sequence, reducing the overall randomness,
which is why it's better to simply continue the original.

 

[Rod Pemberton]

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. This is patently false. A simple 2d plot of a
pseudo-random number generator reveals that the generated pattern of the
numbers is static. And, therefore, the randomness is independent of the
number of calls to rand(), but dependent on the algorithm. Since most
pseudo-random number generators have mathematical defects, such as repeated
numbers, skipped numbers, clustering of non-random numbers, etc., this means
that some numbers have a high probability (or chance) of occuring and others
have a low probability of occuring. Since a 2d plot of the values is
static and we don't care what it looks like, one can visualize it using a
chessboard or checkerboard pattern. Now, if the origin is at (0,0) before
calling srand() and changes to (-0.5,-0.75) after calling srand(), what
happened? The pattern in which the numbers are generated didn't change.
It's still a chessboard or checkerboard or whatever, but the pattern is
shifted. However, the _set_ of numbers which generate that chessboard or
checkerboard did change. 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.


Hope that helps,

Rod Pemberton

 

[Keith Thompson]

True. I stand corrected.


Why'd you recommend it? At least, thats how I took your statement...

It's common to write a function name followed by empty parenthese to
emphasize the fact that it's a function name. When I wrote "calling
srand()", I merely meant "calling the srand function".

[snip]

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

Disagree with me if you like, but don't try to tell me what I meant.
I meant exactly what I wrote.

Yes, calling srand() again with a different seed value will obviously
generate a different pseudo-random sequence. I'm merely saying that
it doesn't make sense to do so. Unless you want to *reproduce* a
pseudo-random sequence, you should call srand() (with some argument)
*once* before any calls to rand(), and use a *single* pseudo-random
sequence for your entire program. Multiple calls to srand() are
likely to cause your random numbers to be less random than they
otherwise would be. (And a second srand(time(NULL)) call within the
same program is likely to re-start the *same* sequence, if both
time(NULL) calls yield the same value; on many systems, this is likely
if the calls are separated by less than one second of real time.)

This is also covered in question 13.17 of the comp.lang.c FAQ, which I
already cited upthread.

 

[A. Sinan Unur]

False.

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

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

This is patently false. A simple 2d
plot of a pseudo-random number generator reveals that the generated
pattern of the numbers is static. And, therefore, the randomness is
independent of the number of calls to rand(), but dependent on the
algorithm.

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

Since most pseudo-random number generators have
mathematical defects, such as repeated numbers, skipped numbers,
clustering of non-random numbers, etc., this means that some numbers
have a high probability (or chance) of occuring and others have a low
probability of occuring. Since a 2d plot of the values is static and
we don't care what it looks like, one can visualize it using a
chessboard or checkerboard pattern. Now, if the origin is at (0,0)
before calling srand() and changes to (-0.5,-0.75) after calling
srand(), what happened? The pattern in which the numbers are
generated didn't change. It's still a chessboard or checkerboard or
whatever, but the pattern is shifted. However, the _set_ of numbers
which generate that chessboard or checkerboard did change. 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.

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?

You are claiming that some specific implementation of rand exhibits
first-order autocorrelation, and proposing to fix the autocorrelation by
repeatedly calling srand. What is the source of the numbers you are
proposing to use to seed the RNG?

Hope that helps,

No thanks.

Sinan

 

[CBFalconer]

.... snip ...

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

None of those are necessarily defects. A random sequence is
expected to produce repeated numbers, skipped numbers, clustering,
etc. There should be probabilities attached to all these cases.

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