473,883 Members | 2,819 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 5229
fieldfallow wrote:
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 ...)

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

Feb 28 '06 #31
Keith Thompson <ks***@mib.or g> writes:
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
Feb 28 '06 #32

Keith Thompson wrote:
"Rod Pemberton" <do*********@so rry.bitbucket.c mm> writes:
"Keith Thompson" <ks***@mib.or g> wrote in message
news:ln******** ****@nuthaus.mi b.org... [...]
<snip>

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

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

Feb 28 '06 #33

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.

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

Feb 28 '06 #34

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?

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


Feb 28 '06 #35
"me********@aol .com" <me********@aol .com> writes:
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.)

--
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.
Feb 28 '06 #36

Keith Thompson wrote:
"Rod Pemberton" <do*********@so rry.bitbucket.c mm> writes:
"Keith Thompson" <ks***@mib.or g> wrote in message
news:ln******** ****@nuthaus.mi b.org... [...]
<snip>

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

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

Feb 28 '06 #37
Rod Pemberton wrote:
"Keith Thompson" <ks***@mib.or g> wrote in message
Calling srand() more than once
makes sense *only* if you want to repeat the same sequence.
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.

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

Feb 28 '06 #38
"Nelu" <ta********@gma il.com> writes:
[...]
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.)

--
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.
Feb 28 '06 #39
On 2006-02-28, Keith Thompson <ks***@mib.or g> wrote:
"me********@aol .com" <me********@aol .com> writes:
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()).


Not quite - Let's suppose, naively, that srand() merely initializes a
particular set of bits of rand()'s internal state, and sets the
remaining bits to zero. Now, if at any point in srand(1)'s sequence, the
internal state contains the result of srand(2) [reasonable if it's
"perfect" i.e. cycles through every possible combination of bits the
internal state could have], srand(1) and srand(2) are thus two different
points in the same sequence.
(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.)

Feb 28 '06 #40

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.