Velocity Reviews > Way for computing random primes in standard C.

Way for computing random primes in standard C.

fieldfallow
Guest
Posts: n/a

 02-24-2006
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
Guest
Posts: n/a

 02-24-2006
In article <dtncv6\$h86\$(E-Mail Removed)>,
fieldfallow <(E-Mail Removed)> wrote:
>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.

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.
--
"No one has the right to destroy another person's belief by
demanding empirical evidence." -- Ann Landers

Kenneth Brody
Guest
Posts: n/a

 02-24-2006
Walter Roberson wrote:
>
> In article <dtncv6\$h86\$(E-Mail Removed)>,
> fieldfallow <(E-Mail Removed)> wrote:
> >Is there a function in the standard C library which returns a prime
> >number which is also pseudo-random?

>
> 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: <(E-Mail Removed)>

Pedro Graca
Guest
Posts: n/a

 02-24-2006
fieldfallow wrote:
> 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
Guest
Posts: n/a

 02-24-2006
Kenneth Brody <(E-Mail Removed)> writes:

> Walter Roberson wrote:
> >
> > In article <dtncv6\$h86\$(E-Mail Removed)>,
> > fieldfallow <(E-Mail Removed)> wrote:
> > >Is there a function in the standard C library which returns a prime
> > >number which is also pseudo-random?

> >
> > No.

>
> 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
Guest
Posts: n/a

 02-24-2006

"fieldfallow" <(E-Mail Removed)> wrote in message
news:dtncv6\$h86\$(E-Mail Removed)...
> 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
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
Guest
Posts: n/a

 02-24-2006
"Rod Pemberton" <(E-Mail Removed)> writes:
[...]
> 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.

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <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.

Rod Pemberton
Guest
Posts: n/a

 02-24-2006

"Keith Thompson" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> "Rod Pemberton" <(E-Mail Removed)> writes:
> [...]
> > 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.

Rod Pemberton

Jordan Abel
Guest
Posts: n/a

 02-24-2006
On 2006-02-24, Rod Pemberton <(E-Mail Removed)> wrote:
>
> "fieldfallow" <(E-Mail Removed)> wrote in message
> news:dtncv6\$h86\$(E-Mail Removed)...
>> 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

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.

>> 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?

Rod Pemberton
Guest
Posts: n/a

 02-25-2006

"Jordan Abel" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> On 2006-02-24, Rod Pemberton <(E-Mail Removed)> wrote:
> >
> > "fieldfallow" <(E-Mail Removed)> wrote in message
> > news:dtncv6\$h86\$(E-Mail Removed)...
> >> 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

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