Way for computing random primes in standard C.

[websnarf@gmail.com]

Re: Way for computing random primes in standard C.

fieldfallow wrote:[color=blue]
> Is there a function in the standard C library which returns a prime
> number which is also pseudo-random?[/color]

No. :) The ANSI C standard doesn't have that sort of content in it.
[color=blue]
> 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.[/color]

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

[color=blue]
> 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?[/color]

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.)
[color=blue]
> Thank you all for the help. I find this group very useful.[/color]

(That is so ironic ...)

--
Paul Hsieh

http://www.pobox.com/~qed/

http://bstring.sf.net/

[Micah Cowan]

Re: Way for computing random primes in standard C.

Keith Thompson <kst-u@mib.org> writes:
[color=blue]
> In your initial contribution to this thread, you wrote:[/color]

(Rod Pemberton wrote:)
[color=blue]
> ] 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?[/color]

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

[Nelu]

Re: Way for computing random primes in standard C.


Keith Thompson wrote:[color=blue]
> "Rod Pemberton" <do_not_have@so rry.bitbucket.c mm> writes:[color=green]
> > "Keith Thompson" <kst-u@mib.org> wrote in message
> > news:lnzmkefzv3 .fsf@nuthaus.mi b.org...[/color]
> [...][color=green][color=darkred]
>>>[/color][/color][/color]
<snip>[color=blue][color=green]
>>[/color][/color]
<snip>[color=blue]
> 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?[/color]
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...)

[Nelu]

Re: Way for computing random primes in standard C.


mensanator@aol. com wrote:[color=blue]
> Rod Pemberton wrote:[color=green]
> >
> > 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().[/color]
>
> No, it's not. There is only ONE sequence.[/color]
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...)

[mensanator@aol.com]

Re: Way for computing random primes in standard C.


Nelu wrote:[color=blue]
> mensanator@aol. com wrote:[color=green]
> > Rod Pemberton wrote:[color=darkred]
> > >
> > > 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().[/color]
> >
> > No, it's not. There is only ONE sequence.[/color]
> 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.[/color]

If I'm wrong, then calling srand() with a constant would not
give you the same sequence, would it?
[color=blue]
>
> --
> Ioan - Ciprian Tandau
> tandau _at_ freeshell _dot_ org (hope it's not too late)
> (... and that it still works...)[/color]

[Keith Thompson]

Re: Way for computing random primes in standard C.

"mensanator@aol .com" <mensanator@aol .com> writes:[color=blue]
> Rod Pemberton wrote:[/color]
[...][color=blue][color=green]
>> "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().[/color]
>
> No, it's not. There is only ONE sequence.
>[color=green]
>> srand() doesn't affect the randomness of values that rand()
>> generates, it only changes the set of generated numbers.[/color]
>
> It does not, as there is only ONE sequence. What srand() does
> is change your position in the sequence.[/color]

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) kst-u@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.

[Nelu]

Re: Way for computing random primes in standard C.


Keith Thompson wrote:[color=blue]
> "Rod Pemberton" <do_not_have@so rry.bitbucket.c mm> writes:[color=green]
> > "Keith Thompson" <kst-u@mib.org> wrote in message
> > news:lnzmkefzv3 .fsf@nuthaus.mi b.org...[/color]
> [...][color=green][color=darkred]
>>>[/color][/color][/color]
<snip>[color=blue][color=green]
>>[/color][/color]
<snip>[color=blue]
> 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?[/color]
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...)

[websnarf@gmail.com]

Re: Way for computing random primes in standard C.

Rod Pemberton wrote:[color=blue]
> "Keith Thompson" <kst-u@mib.org> wrote in message[color=green]
> > Calling srand() more than once
> > makes sense *only* if you want to repeat the same sequence.[/color]
>
> False.[/color]

Right -- but your response is not correct either.
[color=blue]
> 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?[/color]

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/

[Keith Thompson]

Re: Way for computing random primes in standard C.

"Nelu" <tandauioan@gma il.com> writes:
[...][color=blue]
> 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.[/color]

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.
[color=blue]
> However, leaving aside the fact that it's unlikely to keep the sequence
> a secret from a good hacker there are two problems:[/color]

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) kst-u@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.

[Jordan Abel]

Re: Way for computing random primes in standard C.

On 2006-02-28, Keith Thompson <kst-u@mib.org> wrote:[color=blue]
> "mensanator@aol .com" <mensanator@aol .com> writes:[color=green]
>> Rod Pemberton wrote:[/color]
> [...][color=green][color=darkred]
>>> "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().[/color]
>>
>> No, it's not. There is only ONE sequence.
>>[color=darkred]
>>> srand() doesn't affect the randomness of values that rand()
>>> generates, it only changes the set of generated numbers.[/color]
>>
>> It does not, as there is only ONE sequence. What srand() does
>> is change your position in the sequence.[/color]
>
> 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()).[/color]

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.
[color=blue]
> (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.)[/color]

[mensanator@aol.com]

Re: Way for computing random primes in standard C.


Keith Thompson wrote:[color=blue]
> "mensanator@aol .com" <mensanator@aol .com> writes:[color=green]
> > Rod Pemberton wrote:[/color]
> [...][color=green][color=darkred]
> >> "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().[/color]
> >
> > No, it's not. There is only ONE sequence.
> >[color=darkred]
> >> srand() doesn't affect the randomness of values that rand()
> >> generates, it only changes the set of generated numbers.[/color]
> >
> > It does not, as there is only ONE sequence. What srand() does
> > is change your position in the sequence.[/color]
>
> 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()).[/color]

When it's stated that
"...the Mersenne Twister as the core generator.
It produces 53-bit precision floats and has a period of 2**19937-1."

Doesn't it mean that there are 2**19937-1 states and if one were
to actually call it 2**19937 times, then one would be right back
where one started regardless of what number srand() was called with?

I was not implying that srand(1) and srand(2) have adjacent states.
But doesn't periodic mean that at whatever state # srand(1) starts in,
it must eventually reach the same state that srand(2) starts in?

So IF the PRNG is periodic AND the same seed gives the same
sequence THEN sequences generated by diffrent srand() calls
must overlap. If wrong, why?

The standard doen't imply that the PRNG must be periodic, does it?
But are there any puely mathematical ones that aren't?
[color=blue]
>
> (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) kst-u@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.[/color]

[Keith Thompson]

Re: Way for computing random primes in standard C.

Jordan Abel <random832@gmai l.com> writes:[color=blue]
> On 2006-02-28, Keith Thompson <kst-u@mib.org> wrote:[/color]
[...][color=blue][color=green]
>> 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()).[/color]
>
> 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.[/color]

Yes, I think you're right.

Suppose rand() has N bits of internal state. If it cycles through all
2**N possible internal states, then you can think of the set of all
states as a closed loop with 2**N nodes; each call to rand() advances
on position along the loop, and each call to srand() jumps to a single
point on the loop. (Ideally the points for different values of
srand() are roughly equally spaced along the loop, maximizing the
uniqueness of each subsequence.)

If the cycle is shorter than 2**N, then the states form some number of
disjoint loops rather than one single loop. A call to rand() would
advance by one position on a single loop, and a call to srand() could
jump to an arbitrary point on any loop.

But as you point out, an RNG that cycles through its entire state is
probably better than one that doesn't (but one that doesn't is
certainly permitted by the standard).

--
Keith Thompson (The_Other_Keit h) kst-u@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.

[John F]

Re: Way for computing random primes in standard C.


<mensanator@aol .com> wrote:[color=blue]
>
> Keith Thompson wrote:[color=green]
>> "mensanator@aol .com" <mensanator@aol .com> writes:[color=darkred]
>>> [...][/color]
>> 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()).[/color]
>
> When it's stated that
> "...the Mersenne Twister as the core generator.
> It produces 53-bit precision floats and has a period of 2**19937-1."
>
> Doesn't it mean that there are 2**19937-1 states and if one were
> to actually call it 2**19937 times, then one would be right back
> where one started regardless of what number srand() was called with?[/color]

Practically: Yes. Did you actually calculate this _high_ exponential?
for each 3.32 in the exponent you may approximately add 1 to an exponent of
10 ...
so you end up with a number of 6000+ Digits.
[color=blue]
> I was not implying that srand(1) and srand(2) have adjacent states.
> But doesn't periodic mean that at whatever state # srand(1) starts in,
> it must eventually reach the same state that srand(2) starts in?[/color]

Exactly.
[color=blue]
> So IF the PRNG is periodic AND the same seed gives the same
> sequence THEN sequences generated by diffrent srand() calls
> must overlap. If wrong, why?[/color]

On the long run I can see this too. Imagine a cycle with two different
starting points...
[color=blue]
> The standard doen't imply that the PRNG must be periodic, does it?
> But are there any puely mathematical ones that aren't?[/color]

PRNG implys imperfection. Use Blum-Blum-Shub
(http://en.wikipedia.org/wiki/Blum_Blum_Shub) or the Mersenne Twister.
Finite precision will always lead to cycles. Period. Somewhen in a very long
run you'll produce the exactly same value that you started off with...
Mathematically you could even use the logistic equation with infinite
precision, of course.

regards
John

[Flash Gordon]

Re: Way for computing random primes in standard C.

Keith Thompson wrote:[color=blue]
> Jordan Abel <random832@gmai l.com> writes:[color=green]
>> On 2006-02-28, Keith Thompson <kst-u@mib.org> wrote:[/color]
> [...][color=green][color=darkred]
>>> 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()).[/color]
>> 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.[/color]
>
> Yes, I think you're right.
>
> Suppose rand() has N bits of internal state. If it cycles through all
> 2**N possible internal states, then you can think of the set of all
> states as a closed loop with 2**N nodes; each call to rand() advances
> on position along the loop, and each call to srand() jumps to a single
> point on the loop. (Ideally the points for different values of
> srand() are roughly equally spaced along the loop, maximizing the
> uniqueness of each subsequence.)
>
> If the cycle is shorter than 2**N, then the states form some number of
> disjoint loops rather than one single loop. A call to rand() would
> advance by one position on a single loop, and a call to srand() could
> jump to an arbitrary point on any loop.
>
> But as you point out, an RNG that cycles through its entire state is
> probably better than one that doesn't (but one that doesn't is
> certainly permitted by the standard).[/color]

Here's an idea. Isn't Pi meant to be a non-repeating series of digits?
See http://www.piworld.de/pi-statistics/ So how about for your PRNG
calculating the digits of Pi in base RAND_MAX+1?

srand could then just select where to start.

This would not be good enough for security, since if anyone knows that
it is producing the digits of Pi all they have to do is identify where
in the sequence you are, but for other uses it should produce an
infinite (as far as we know) sequence of numbers with very good
statistical properties.

It might also not be the most efficient method of producing random numbers.

Note that I am *not* an expert on statistics, Pi, or PRNGs.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:

http://clc-wiki.net/wiki/Intro_to_clc

[Ben Bacarisse]

Re: Way for computing random primes in standard C.

On Mon, 27 Feb 2006 21:19:19 -0800, websnarf wrote:
[color=blue]
> 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.[/color]

time and getpid will give you way less than 64 bits of entropy. The
exact amount will depend on the program and system execution pattern so I
would not like to hazard a guess, but I'd be surprised if together you
could get more than a handful of bits of entropy from them.
[color=blue]
> Other common practical
> sources are things like the value of clock() in response to input device
> interrupts (like keyboard or mouse inputs.)[/color]

<OT>Many systems have a driver that "harvests" the entropy from such
events. If you don't have this, hashing the system's process table
might be easier.</OT>
[color=blue]
> As one final comment -- using the ANSI C's rand() is bad because the
> state size is so small[/color]

I don't think the standard mandates any state size, does it? I don't
think there is nothing to stop rand() being a very high quality generator.

--
Ben.