473,883 Members | 1,772 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 5228
Walter Roberson wrote:
In article <sl************ *******@ID-203069.user.ind ividual.net>,
Pedro Graca <he****@hotpop. com> wrote:


Why copy the "Reply-To:" address and not the "From:" one?

It's ok :)
If I didn't want the address public I wouldn't use it; I just found it
strange to see this old address in a new post and thought my
configuration was messed up :)

--
If you're posting through Google read <http://cfaj.freeshell. org/google>
Mar 3 '06 #91
On Thu, 02 Mar 2006 23:26:07 GMT, Micah Cowan <mi***@cowan.na me>
wrote:
>

Perhaps you should not have made it appear to be a comment on what
Keith wrote, then. I thought you intended something more than just a
random injection of a truism.


It was a comment on what he wrote. My point is that calling srand()
more than once /can/ have purposes beyond repeating the same sequence
of pseudo-random numbers, contrary to what Keith implied. Is no one on
this thread actually reading before they post?


Don't assume that those who don't agree with you just aren't reading
properly. I understand what Rod (and apparently you) is suggesting, I
just don't agree. I do agree with Keith (and others) that restarting
the sequence is as least as likely to decrease randomness as improve
it. I also agree that if staying with the same seed isn't random
enough for your purposes, then you need a better generator, rather
than repeatedly poking at the one you've got. Calling srand() multiple
times can only complicate the analysis.

--
Al Balmer
Sun City, AZ
Mar 3 '06 #92
Micah Cowan <mi***@cowan.na me> wrote in
news:87******** ****@mcowan.bar racudanetworks. com:
Al Balmer <al******@att.n et> writes:
On Thu, 02 Mar 2006 21:46:46 GMT, Micah Cowan <mi***@cowan.na me>
wrote:
>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.
> Perhaps you should not have made it appear to be a comment on what
Keith wrote, then. I thought you intended something more than just a
random injection of a truism.


....
I don't agree, generally, with what Rod's suggesting, but I was trying
to at least clarify that his point was rather different from what was
being claimed by others (Sinan still seems confused, at least), and
What am I confused about?

1) Calling srand multiple times in the program is only appropriate if it
is called with the same value each time so as to repeat a random
sequence (say, if you are running a simulation).

2) Calling srand multiple times with different values, on the other
hand, is a sure sign of confusion.
could actually be good advice in some very limited situations (in
applications such as he described [card games] and with /extremely/
poor PRNGs, or a very long-lived card player ;-) ).


If the RNG is that poor, one should use another one, rather than trying
to play tricks with srand.

The main reason srand exists is to provide repeatable results in
scientific applications.

Sinan
--
A. Sinan Unur <1u**@llenroc.u de.invalid>
(reverse each component and remove .invalid for email address)
Mar 3 '06 #93
Micah Cowan <mi***@cowan.na me> wrote in
news:87******** ****@mcowan.bar racudanetworks. com:
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.


ITYM 'scientifically '. In science, replicability of results is crucial.

Sinan
--
A. Sinan Unur <1u**@llenroc.u de.invalid>
(reverse each component and remove .invalid for email address)
Mar 3 '06 #94
Keith Thompson <ks***@mib.or g> writes:
Micah Cowan <mi***@cowan.na me> writes:
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.


It doesn't follow as a matter of rigorous deductive reasoning, but it
seems to me to be a reasonable common-sense inference. Any decent
pseudo-random number generator is going to be designed to work best
when it's allowed to generate a sequence from a starting seed without
interference. If you try to second-guess the algorithm by arbitrarily
perturbing it with additional calls to srand(), there is no reason to
think that the result is going to be any better (whatever "better"
means). If you *know* that re-seeding the algorithm will generate
better results, that implies, I think, that the algorithm is
defective, and you should just use a better one (many are freely
available). A re-seeding scheme that improves one RNG is unlikely to
improve another RNG, so any code that does something like this is
going to be gratuitously non-portable anyway. Using a different RNG
doesn't even sacrifice portability; numerous RNGs are available in
portable C code.


I think the above is extremely well put.
Mar 3 '06 #95
Keith Thompson <ks***@mib.or g> writes:
Micah Cowan <mi***@cowan.na me> writes:
Al Balmer <al******@att.n et> writes:
On Thu, 02 Mar 2006 21:23:29 GMT, Micah Cowan <mi***@cowan.na me>
wrote: [...] >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.


There are perfectly legitimate reasons to repeat the same sequence for
some applications, and there's nothing necessarily stupid about doing
so.


Absolutely.
That's why the standard specifies that behavior. Your
introduction of the word "stupidly" was, shall we say, less than
illuminating to the discussion.


What I mean is, it would be stupid to do so in the context we've been
talking about. I'm sorry if it came across otherwise.

To be as clear as possible, what I meant is: if one proposes to call
srand() multiple times throughout a program's lifetime for the purpose
of "improving randomness", then doing so with the same input each time
would be stupid; however, doing so with different inputs wouldn't
necessarily be a terrible idea in some limited situations.

It's obviously not stupid to call srand() with the same input to
reproduce a given sequence, and I did not mean to suggest so.
Mar 3 '06 #96
"A. Sinan Unur" <1u**@llenroc.u de.invalid> writes:
Micah Cowan <mi***@cowan.na me> wrote in
I don't agree, generally, with what Rod's suggesting, but I was trying
to at least clarify that his point was rather different from what was
being claimed by others (Sinan still seems confused, at least), and


What am I confused about?


From the posts that I've read, and from your recently posted code
(upstream), you were making a case against calling srand() (or more
accurately, after) each call to rand(). However, to my knowledge,
nobody was making a case /for/ such behavior.
1) Calling srand multiple times in the program is only appropriate if it
is called with the same value each time so as to repeat a random
sequence (say, if you are running a simulation).
I think everyone's agreeing here.
2) Calling srand multiple times with different values, on the other
hand, is a sure sign of confusion.
could actually be good advice in some very limited situations (in
applications such as he described [card games] and with /extremely/
poor PRNGs, or a very long-lived card player ;-) ).
If the RNG is that poor, one should use another one, rather than trying
to play tricks with srand.


Yes, that would be my preference as well. I would personally never do
as Rod has suggested; I was only trying to point out that he wasn't
completely without a point.
The main reason srand exists is to provide repeatable results in
scientific applications.


Hm. Given rand()'s implementation track-record, I can't think of many
scientific applications in which I would be comfortable using it
(though I don't doubt for a moment the truth of what you say).

OTOH, I have made frequent use of it when writing games. :-)
Mar 3 '06 #97
Micah Cowan <mi***@cowan.na me> writes:
Keith Thompson <ks***@mib.or g> writes:

[...]
There are perfectly legitimate reasons to repeat the same sequence for
some applications, and there's nothing necessarily stupid about doing
so.


Absolutely.
That's why the standard specifies that behavior. Your
introduction of the word "stupidly" was, shall we say, less than
illuminating to the discussion.


What I mean is, it would be stupid to do so in the context we've been
talking about. I'm sorry if it came across otherwise.

To be as clear as possible, what I meant is: if one proposes to call
srand() multiple times throughout a program's lifetime for the purpose
of "improving randomness", then doing so with the same input each time
would be stupid; however, doing so with different inputs wouldn't
necessarily be a terrible idea in some limited situations.

It's obviously not stupid to call srand() with the same input to
reproduce a given sequence, and I did not mean to suggest so.


Agreed, and again, thanks for the clarification.

Just to be even clearer, I don't recall anyone suggesting that srand()
should be called again with the same seed for the purpose of improving
randomness (though someone may well have have mistakenly thought that
someone else had suggested it).

Which is not intended to suggest that *you* necessarily suggested that
anyone had suggested it, merely that <POOF> oh, crud, there goes my
last brain cell.

--
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 3 '06 #98
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


No such guarantee. If you want a completely controlled random
generator, supply your own. For an example of this, see the test
program for my hashlib package, which uses a Mersenne Twister
generator. That way I can supply regression tests by comparing
tester output with my own output.

<http://cbfalconer.home .att.net/download/hashlib.zip>

--
"If you want to post a followup via groups.google.c om, 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/googlegroupsrep ly/>
Mar 3 '06 #99
In article <sl************ *******@ID-203069.user.ind ividual.net>,
Pedro Graca <he****@hotpop. com> wrote:
Walter Roberson wrote:
In article <sl************ *******@ID-203069.user.ind ividual.net>,
Pedro Graca <he****@hotpop. com> wrote:
Why copy the "Reply-To:" address and not the "From:" one?


It was automatic by my newsreader. I'd guess it picks that one
as part of the same logic that prepares the address for Cc:
or email reply purposes.
--
Prototypes are supertypes of their clones. -- maplesoft
Mar 3 '06 #100

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.