473,883 Members | 2,961 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
"Rod Pemberton" <do*********@so rry.bitbucket.c mm> wrote in
news:du******** **@news3.infoav e.net:
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

--
A. Sinan Unur <1u**@llenroc.u de.invalid>
(reverse each component and remove .invalid for email address)

comp.lang.perl. misc guidelines on the WWW:
http://mail.augustmail.com/~tadmc/cl...uidelines.html

Mar 2 '06 #71
Keith Thompson <ks***@mib.or g> writes:
"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.


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
Mar 2 '06 #72
Micah Cowan <mi***@cowan.na me> writes:
Keith Thompson <ks***@mib.or g> writes:
"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.


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 (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 #73
Keith Thompson <ks***@mib.or g> writes:
[...]
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().

--
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 #74
[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
--
If you're posting through Google read <http://cfaj.freeshell. org/google>
Mar 2 '06 #75
Keith Thompson <ks***@mib.or g> writes:
Micah Cowan <mi***@cowan.na me> writes:
Keith Thompson <ks***@mib.or g> writes:
"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.
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.
Mar 2 '06 #76
Pedro Graca <he****@dodgeit .com> writes:
[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
Mar 2 '06 #77
Pedro Graca wrote:
[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.

--
BR, Vladimir

Don't quit now, we might just as well
lock the door and throw away the key.

Mar 2 '06 #78
On Thu, 02 Mar 2006 21:23:29 GMT, Micah Cowan <mi***@cowan.na me>
wrote:
Keith Thompson <ks***@mib.or g> writes:
Micah Cowan <mi***@cowan.na me> writes:
> Keith Thompson <ks***@mib.or g> writes:

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.

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

--
Al Balmer
Sun City, AZ
Mar 2 '06 #79
Al Balmer <al******@att.n et> writes:
On Thu, 02 Mar 2006 21:23:29 GMT, Micah Cowan <mi***@cowan.na me>
wrote:
Keith Thompson <ks***@mib.or g> writes:
Micah Cowan <mi***@cowan.na me> writes:
> Keith Thompson <ks***@mib.or g> writes:
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.

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

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.