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.
104  5016 
In article <dt**********@emma.aioe.org>,
fieldfallow <fi*********@gmail.com> 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.
'better' would depend upon the density of access to the array.
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
Walter Roberson wrote:
In article <dt**********@emma.aioe.org>,
fieldfallow <fi*********@gmail.com> 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: <mailto:Th*************@gmail.com>
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.
--
If you're posting through Google read <http://cfaj.freeshell.org/google>
Kenneth Brody <ke******@spamcop.net> writes: Walter Roberson wrote:
In article <dt**********@emma.aioe.org>,
fieldfallow <fi*********@gmail.com> 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.
"fieldfallow" <fi*********@gmail.com> wrote in message
news:dt**********@emma.aioe.org... 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
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
"Rod Pemberton" <do*********@sorry.bitbucket.cmm> 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) 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.
"Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org... "Rod Pemberton" <do*********@sorry.bitbucket.cmm> 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
On 2006-02-24, Rod Pemberton <do*********@sorry.bitbucket.cmm> wrote:
"fieldfallow" <fi*********@gmail.com> wrote in message
news:dt**********@emma.aioe.org... 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?
"Jordan Abel" <ra*******@gmail.com> wrote in message
news:sl***********************@random.yi.org... On 2006-02-24, Rod Pemberton <do*********@sorry.bitbucket.cmm> wrote:
"fieldfallow" <fi*********@gmail.com> wrote in message
news:dt**********@emma.aioe.org... 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
"Micah Cowan" <mi***@cowan.name> wrote in message
news:87************@mcowan.barracudanetworks.com.. . Kenneth Brody <ke******@spamcop.net> writes:
Walter Roberson wrote:
In article <dt**********@emma.aioe.org>,
fieldfallow <fi*********@gmail.com> 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.
Well, i believe that the OP intended to hardcode an array initialization to
some available list of primes. The first millions of primes have been
already computed, there is no need to do that again as it is time consuming.
The OP could have a large number of primes stored in a file and read up to
RAND_MAX primes into an array each time the program executes. If RAND_MAX
does not vary between program executions and is relatively small, primes can
be hardcoded in the source file. Maybe time saving can make up for space
loss.
Many primes can be found here: http://primes.utm.edu
"Rod Pemberton" <do*********@sorry.bitbucket.cmm> writes: "Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org... "Rod Pemberton" <do*********@sorry.bitbucket.cmm> 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.
You might consider reading some documentation before you post.
Calling srand() without arguments is illegal. It expects a single
argument of type unsigned int. In C90, you could call it with no
arguments if you didn't have a "#include <stdlib.h>", but that would
invoke undefined behavior.
Here's what the standard says (C99 7.20.2.2p2):
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.
Question 13.17 in the comp.lang.c FAQ also has some good information.
Calling srand(time(NULL)) exactly *once* before calling rand() is a
reasonable way to get decent random numbers (though if you want really
good random numbers you need to use something better than rand()).
Calling srand() with a constant argument gives you a reproducible
sequence of pseudo-random numbers. Calling srand() more than once
makes sense *only* if you want to repeat the same sequence.
--
Keith Thompson (The_Other_Keith) 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.
"Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org... "Rod Pemberton" <do*********@sorry.bitbucket.cmm> writes: "Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org... "Rod Pemberton" <do*********@sorry.bitbucket.cmm> 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.
You might consider reading some documentation before you post.
Calling srand() without arguments is illegal.
True. I stand corrected.
It expects a single
argument of type unsigned int. In C90, you could call it with no
arguments if you didn't have a "#include <stdlib.h>", but that would
invoke undefined behavior.
Why'd you recommend it? At least, thats how I took your statement...
<snip>
Calling srand(time(NULL)) exactly *once* before calling rand() is a
reasonable way to get decent random numbers
True.
(though if you want really
good random numbers you need to use something better than rand()).
True.
Calling srand() with a constant argument gives you a reproducible
sequence of pseudo-random numbers.
True.
Calling srand() more than once
makes sense *only* if you want to repeat the same sequence.
False.
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?
Rod Pemberton
"Rod Pemberton" <do*********@sorry.bitbucket.cmm> wrote in
news:dt***********@news3.infoave.net:
"Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org...
....
Calling srand() more than once
makes sense *only* if you want to repeat the same sequence.
False.
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.'"
You are misreading Keith's post. Calling srand multiple times with
different seeds during the life time of the program *decreases* the
randomness of the sequence generated.
So, it does not make sense to call srand multiple times unless you want
to repeat the same sequence.
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?
Thanks, but no thanks. I know that you would switch to a different
sequence, I am sure Keith knows that you would switch to a different
sequence. But, it is still not the sensible thing to do.
Sinan
--
A. Sinan Unur <1u**@llenroc.ude.invalid>
(reverse each component and remove .invalid for email address)
Rod Pemberton wrote: 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.
But what's the advantage of starting a new sequence,
over just simply continuing on with the old sequence?
--
pete
pete wrote: Rod Pemberton wrote:
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.
But what's the advantage of starting a new sequence,
over just simply continuing on with the old sequence?
No advantage. And the "different" sequence may, in fact,
overlap the original sequence, reducing the overall randomness,
which is why it's better to simply continue the original.
--
pete
"A. Sinan Unur" <1u**@llenroc.ude.invalid> wrote in message
news:Xn****************************@127.0.0.1... "Rod Pemberton" <do*********@sorry.bitbucket.cmm> wrote in
news:dt***********@news3.infoave.net:
"Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org...
...
Calling srand() more than once
makes sense *only* if you want to repeat the same sequence.
False.
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.'"
You are misreading Keith's post. Calling srand multiple times with
different seeds during the life time of the program *decreases* the
randomness of the sequence generated.
False.
What you are claiming is that the randomness of the sequence increases as
the rand() function is used. This is patently false. A simple 2d plot of a
pseudo-random number generator reveals that the generated pattern of the
numbers is static. And, therefore, the randomness is independent of the
number of calls to rand(), but dependent on the algorithm. Since most
pseudo-random number generators have mathematical defects, such as repeated
numbers, skipped numbers, clustering of non-random numbers, etc., this means
that some numbers have a high probability (or chance) of occuring and others
have a low probability of occuring. Since a 2d plot of the values is
static and we don't care what it looks like, one can visualize it using a
chessboard or checkerboard pattern. Now, if the origin is at (0,0) before
calling srand() and changes to (-0.5,-0.75) after calling srand(), what
happened? The pattern in which the numbers are generated didn't change.
It's still a chessboard or checkerboard or whatever, but the pattern is
shifted. However, the _set_ of numbers which generate that chessboard or
checkerboard did change. By calling srand() we increased the probability of
some numbers which had low probability and reduced the probability of other
numbers which had low probability.
Hope that helps,
Rod Pemberton
"Rod Pemberton" <do*********@sorry.bitbucket.cmm> writes: "Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org... "Rod Pemberton" <do*********@sorry.bitbucket.cmm> writes: > "Keith Thompson" <ks***@mib.org> wrote in message
[snip] >> 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.
You might consider reading some documentation before you post.
Calling srand() without arguments is illegal.
True. I stand corrected.
It expects a single
argument of type unsigned int. In C90, you could call it with no
arguments if you didn't have a "#include <stdlib.h>", but that would
invoke undefined behavior.
Why'd you recommend it? At least, thats how I took your statement...
It's common to write a function name followed by empty parenthese to
emphasize the fact that it's a function name. When I wrote "calling
srand()", I merely meant "calling the srand function".
[snip] Calling srand() more than once
makes sense *only* if you want to repeat the same sequence.
False.
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?
Disagree with me if you like, but don't try to tell me what I meant.
I meant exactly what I wrote.
Yes, calling srand() again with a different seed value will obviously
generate a different pseudo-random sequence. I'm merely saying that
it doesn't make sense to do so. Unless you want to *reproduce* a
pseudo-random sequence, you should call srand() (with some argument)
*once* before any calls to rand(), and use a *single* pseudo-random
sequence for your entire program. Multiple calls to srand() are
likely to cause your random numbers to be less random than they
otherwise would be. (And a second srand(time(NULL)) call within the
same program is likely to re-start the *same* sequence, if both
time(NULL) calls yield the same value; on many systems, this is likely
if the calls are separated by less than one second of real time.)
This is also covered in question 13.17 of the comp.lang.c FAQ, which I
already cited upthread.
--
Keith Thompson (The_Other_Keith) 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.
"Rod Pemberton" <do*********@sorry.bitbucket.cmm> wrote in
news:dt***********@news3.infoave.net:
"A. Sinan Unur" <1u**@llenroc.ude.invalid> wrote in message
news:Xn****************************@127.0.0.1... "Rod Pemberton" <do*********@sorry.bitbucket.cmm> wrote in
news:dt***********@news3.infoave.net:
>
> "Keith Thompson" <ks***@mib.org> wrote in message
> news:ln************@nuthaus.mib.org...
...
>> Calling srand() more than once
>> makes sense *only* if you want to repeat the same sequence.
>
> False.
>
> 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.'"
You are misreading Keith's post. Calling srand multiple times with
different seeds during the life time of the program *decreases* the
randomness of the sequence generated.
False.
What you are claiming is that the randomness of the sequence increases
as the rand() function is used.
That is not what I am claiming at all. You are misreading my post as
well as Keith's.
This is patently false. A simple 2d
plot of a pseudo-random number generator reveals that the generated
pattern of the numbers is static. And, therefore, the randomness is
independent of the number of calls to rand(), but dependent on the
algorithm.
Of course it is. But if the algorithm is hosed, how can calling srand
multiple times help?
Since most pseudo-random number generators have
mathematical defects, such as repeated numbers, skipped numbers,
clustering of non-random numbers, etc., this means that some numbers
have a high probability (or chance) of occuring and others have a low
probability of occuring. Since a 2d plot of the values is static and
we don't care what it looks like, one can visualize it using a
chessboard or checkerboard pattern. Now, if the origin is at (0,0)
before calling srand() and changes to (-0.5,-0.75) after calling
srand(), what happened? The pattern in which the numbers are
generated didn't change. It's still a chessboard or checkerboard or
whatever, but the pattern is shifted. However, the _set_ of numbers
which generate that chessboard or checkerboard did change. By calling
srand() we increased the probability of some numbers which had low
probability and reduced the probability of other numbers which had low
probability.
You have introduced a chicken-and-egg problem here: To get appropriately
random numbers, you are claiming, one needs to keep reseeding the random
number generator with appropriately random numbers. Huh?
You are claiming that some specific implementation of rand exhibits
first-order autocorrelation, and proposing to fix the autocorrelation by
repeatedly calling srand. What is the source of the numbers you are
proposing to use to seed the RNG?
Hope that helps,
No thanks.
Sinan
--
A. Sinan Unur <1u**@llenroc.ude.invalid>
(reverse each component and remove .invalid for email address)
"A. Sinan Unur" wrote: "Rod Pemberton" <do*********@sorry.bitbucket.cmm> wrote:
.... snip ...
Of course it is. But if the algorithm is hosed, how can calling
srand multiple times help?
Since most pseudo-random number generators have
mathematical defects, such as repeated numbers, skipped numbers,
clustering of non-random numbers, etc., this means that some
numbers have a high probability (or chance) of occuring and
others have a low probability of occuring. Since a 2d plot of
None of those are necessarily defects. A random sequence is
expected to produce repeated numbers, skipped numbers, clustering,
etc. There should be probabilities attached to all these cases.
--
"If you want to post a followup via groups.google.com, 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/googlegroupsreply/>
"Rod Pemberton" <do*********@sorry.bitbucket.cmm> writes: "A. Sinan Unur" <1u**@llenroc.ude.invalid> wrote in message
news:Xn****************************@127.0.0.1... "Rod Pemberton" <do*********@sorry.bitbucket.cmm> wrote in
news:dt***********@news3.infoave.net: > "Keith Thompson" <ks***@mib.org> wrote in message
> news:ln************@nuthaus.mib.org... ... >> Calling srand() more than once
>> makes sense *only* if you want to repeat the same sequence.
>
> False.
>
> 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.'"
You are misreading Keith's post. Calling srand multiple times with
different seeds during the life time of the program *decreases* the
randomness of the sequence generated.
False.
What you are claiming is that the randomness of the sequence increases as
the rand() function is used.
No, nobody made that claim.
[snip]
By calling srand() we increased the probability of
some numbers which had low probability and reduced the probability of other
numbers which had low probability.
So you're asserting that repeatedly calling srand() improves the
randomness of the numbers returned by rand()? In particular, you're
claming that that something like this:
int rand_array[SOME_SIZE];
int index = 0;
srand(some_value);
rand_array[index++] = rand();
rand_array[index++] = rand();
rand_array[index++] = rand();
srand(some_other_value);
rand_array[index++] = rand();
rand_array[index++] = rand();
rand_array[index++] = rand();
is likely to yield better (more random) results than if the second
call to srand() were removed (perhaps with a different number of
calls)?
If this is correct, then there's an error in the comp.lang.c FAQ,
question 13.17. If you can convince Steve Summit that this is an
error, I'm sure he'll be willing to change it. You'll need to support
your claim with concrete evidence, of course. It would also be
interesting to know how often, under what circumstances, and with what
arguments srand() should be called to get the best possible
pseudo-random numbers. (I happen to think that you're completely
wrong, but I've been mistaken before.)
If I've misunderstand what you're claiming, please clarify.
--
Keith Thompson (The_Other_Keith) 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.
Keith Thompson wrote:
.... snip ...
So you're asserting that repeatedly calling srand() improves the
randomness of the numbers returned by rand()? In particular, you're
claming that that something like this:
int rand_array[SOME_SIZE];
int index = 0;
srand(some_value);
rand_array[index++] = rand();
rand_array[index++] = rand();
rand_array[index++] = rand();
srand(some_other_value);
rand_array[index++] = rand();
rand_array[index++] = rand();
rand_array[index++] = rand();
is likely to yield better (more random) results than if the second
call to srand() were removed (perhaps with a different number of
calls)?
If this is correct, then there's an error in the comp.lang.c FAQ,
question 13.17. If you can convince Steve Summit that this is an
error, I'm sure he'll be willing to change it. You'll need to support
your claim with concrete evidence, of course. It would also be
interesting to know how often, under what circumstances, and with what
arguments srand() should be called to get the best possible
pseudo-random numbers. (I happen to think that you're completely
wrong, but I've been mistaken before.)
It could happen with particularly bad random number generators.
For example, some algorithms can get into multiple independant
cycles, of different lengths. However even Microsoft is not likely
to use these algorithms.
--
"If you want to post a followup via groups.google.com, 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/googlegroupsreply/>
CBFalconer <cb********@yahoo.com> writes: Keith Thompson wrote:
[snip] It could happen with particularly bad random number generators.
For example, some algorithms can get into multiple independant
cycles, of different lengths. However even Microsoft is not likely
to use these algorithms.
As far as I know the sample implementation in the standard doesn't
have that flaw, and there's no excuse for using an implementation
worse than that.
--
Keith Thompson (The_Other_Keith) 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.
On Sun, 26 Feb 2006 05:33:36 +0000, Keith Thompson wrote: By calling srand() we increased the
probability of
some numbers which had low probability and reduced the probability of
other numbers which had low probability.
So you're asserting that repeatedly calling srand() improves the
randomness of the numbers returned by rand()? In particular, you're
claming that that something like this:
int rand_array[SOME_SIZE];
int index = 0;
srand(some_value);
rand_array[index++] = rand();
rand_array[index++] = rand();
rand_array[index++] = rand();
srand(some_other_value);
rand_array[index++] = rand();
rand_array[index++] = rand();
rand_array[index++] = rand();
is likely to yield better (more random) results than if the second call to
srand() were removed (perhaps with a different number of calls)?
There is a degenerate case where you will almost certainly get better
"randomness": by calling srand with a seed chosen by a high-quality
hardware RNG before every call to rand. (I say almost because the
transformation from srand to the result of rand just *might* be
pathologically bad.)
Obviously, this case is absurd (just use your better source) but it is
possible (I'll put it no more strongly than that) that in cases where the
entropy of your source is precious you might get some improvement by
calling srand with a new random seed for every nth call to rand (for n >
1). If we use n==0 for the case where we use our source directly, then
we have a continuity from n==0 giving good randomness but using up our
precious entropy, to n==inf where we use none of it and rely on rand
entirely. The optimal point (if there is one) will depend on
circumstances.
However (and it is a big however) as someone who has worked on RNGs for
cryptographic applications I would not recommend this technique at all!
The reason is that the effort involved in studying the algorithm used by
srand/rand to ensure that is does not introduce any serious flaws in the
random number stream is just too great. If you need a very high quality
stream, there are plenty of open source implementations available (with
supporting analysis). If you don't them using rand (with srand called
once at the start) will do just fine. Interleaving calls to srand will
cause the reader to wonder if you have made things mysteriously worse,
even though it might well be helping a little.
In short, I agree with you that it is a Bad Idea.
--
Ben.
Keith Thompson wrote:
"Rod Pemberton" <do*********@sorry.bitbucket.cmm> writes:
[...] By calling srand() we increased the probability of
some numbers which had low probability and reduced the probability of other
numbers which had low probability.
So you're asserting that repeatedly calling srand() improves the
randomness of the numbers returned by rand()? In particular, you're
claming that that something like this:
int rand_array[SOME_SIZE];
int index = 0;
srand(some_value);
rand_array[index++] = rand();
[...] srand(some_other_value);
rand_array[index++] = rand();
[...]
is likely to yield better (more random) results than if the second
call to srand() were removed (perhaps with a different number of
calls)?
[...]
I know someone who did (in a language other than C) the equivalent of:
int MyRandomNumber(void)
{
int ret;
srand(ret = rand());
return(ret);
}
(ie: constantly re-seeding the generator with the previous return value)
and then complained about the low-randomness.
--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:Th*************@gmail.com>
"A. Sinan Unur" <1u**@llenroc.ude.invalid> wrote in message
news:Xn****************************@127.0.0.1... "Rod Pemberton" <do*********@sorry.bitbucket.cmm> wrote in
news:dt***********@news3.infoave.net:
"A. Sinan Unur" <1u**@llenroc.ude.invalid> wrote in message
news:Xn****************************@127.0.0.1... "Rod Pemberton" <do*********@sorry.bitbucket.cmm> wrote in
news:dt***********@news3.infoave.net:
>
> "Keith Thompson" <ks***@mib.org> wrote in message
> news:ln************@nuthaus.mib.org...
...
>> Calling srand() more than once
>> makes sense *only* if you want to repeat the same sequence.
>
> False.
>
> 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.'"
You are misreading Keith's post. Calling srand multiple times with
different seeds during the life time of the program *decreases* the
randomness of the sequence generated.
False.
What you are claiming is that the randomness of the sequence increases
as the rand() function is used.
That is not what I am claiming at all. You are misreading my post as
well as Keith's.
Fine... This is patently false. A simple 2d
plot of a pseudo-random number generator reveals that the generated
pattern of the numbers is static. And, therefore, the randomness is
independent of the number of calls to rand(), but dependent on the
algorithm.
Of course it is. But if the algorithm is hosed, how can calling srand
multiple times help?
The algorithm isn't "hosed." It's just not a random number generator. It's
pseudo-random. Since most pseudo-random number generators have
mathematical defects, such as repeated numbers, skipped numbers,
clustering of non-random numbers, etc., this means that some numbers
have a high probability (or chance) of occuring and others have a low
probability of occuring. Since a 2d plot of the values is static and
we don't care what it looks like, one can visualize it using a
chessboard or checkerboard pattern. Now, if the origin is at (0,0)
before calling srand() and changes to (-0.5,-0.75) after calling
srand(), what happened? The pattern in which the numbers are
generated didn't change. It's still a chessboard or checkerboard or
whatever, but the pattern is shifted. However, the _set_ of numbers
which generate that chessboard or checkerboard did change. By calling
srand() we increased the probability of some numbers which had low
probability and reduced the probability of other numbers which had low
probability.
You have introduced a chicken-and-egg problem here: To get appropriately
random numbers, you are claiming, one needs to keep reseeding the random
number generator with appropriately random numbers. Huh?
If I was misreading before, you are now. 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(). srand() doesn't affect
the randomness of values that rand() generates, it only changes the set of
generated numbers. Since the algorithm isn't a perfect-random number
generator but a pseudo-random number generator, the probabilities of certain
numbers occurring is higher than others. These probabilities can be shifted
by calls to srand().
Rod Pemberton
"Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org... "Rod Pemberton" <do*********@sorry.bitbucket.cmm> writes: "A. Sinan Unur" <1u**@llenroc.ude.invalid> wrote in message
news:Xn****************************@127.0.0.1... "Rod Pemberton" <do*********@sorry.bitbucket.cmm> wrote in
news:dt***********@news3.infoave.net:
> "Keith Thompson" <ks***@mib.org> wrote in message
> news:ln************@nuthaus.mib.org...
...
>> Calling srand() more than once
>> makes sense *only* if you want to repeat the same sequence.
>
> False.
>
> 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.'"
You are misreading Keith's post. Calling srand multiple times with
different seeds during the life time of the program *decreases* the
randomness of the sequence generated.
False.
What you are claiming is that the randomness of the sequence increases
as the rand() function is used.
No, nobody made that claim.
[snip]
By calling srand() we increased the
probability of some numbers which had low probability and reduced the probability of
other numbers which had low probability.
So you're asserting that repeatedly calling srand() improves the
randomness of the numbers returned by rand()? In particular, you're
claming that that something like this:
<snip> is likely to yield better (more random) results than if the second
call to srand() were removed (perhaps with a different number of
calls)?
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(). srand() doesn't affect the randomness of values that rand()
generates, it only changes the set of generated numbers. Since the
algorithm isn't a perfect-random number generator but a pseudo-random number
generator, the probabilities of certain numbers occurring is higher than
others. These probabilities can be shifted by calls to srand(). "
Rod Pemberton
"Rod Pemberton" <do*********@sorry.bitbucket.cmm> writes: "Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org...
[...] So you're asserting that repeatedly calling srand() improves the
randomness of the numbers returned by rand()? In particular, you're
claming that that something like this:
<snip> is likely to yield better (more random) results than if the second
call to srand() were removed (perhaps with a different number of
calls)?
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(). srand() doesn't affect the randomness of values that rand()
generates, it only changes the set of generated numbers. Since the
algorithm isn't a perfect-random number generator but a pseudo-random number
generator, the probabilities of certain numbers occurring is higher than
others. These probabilities can be shifted by calls to srand(). "
The fact that rand() is a pseudo-random number generator does not
imply that certain numbers appear with a higher probability than
others. For example, if RAND_MAX==32767, it's entirely possible that
each of the 32768 possible values will appear with exactly equal
probability over the long run, for each possible seed. (The generator
can still be imperfectly random even if this is true. For example,
rand() is likely to repeat over a cycle whose length depends on the
size of its internal state; a true random number generator would not
do so, though over the very long run it will sometimes appear to do
so.)
Or have I misunderstood what you meant by "the probabilities of
certain numbers occurring is higher than others"?
In your initial contribution to this thread, you 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?
Note that inserting an extra call to rand() will also change the
behavior of subsequent calls to rand(); would that suit your purpose
as well?
--
Keith Thompson (The_Other_Keith) 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.
"Rod Pemberton" <do*********@sorry.bitbucket.cmm> wrote in
news:du***********@news3.infoave.net: "Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org... "Rod Pemberton" <do*********@sorry.bitbucket.cmm> writes: > "A. Sinan Unur" <1u**@llenroc.ude.invalid> wrote in message
> news:Xn****************************@127.0.0.1...
>> "Rod Pemberton" <do*********@sorry.bitbucket.cmm> wrote in
>> news:dt***********@news3.infoave.net:
>> > "Keith Thompson" <ks***@mib.org> wrote in message
>> > news:ln************@nuthaus.mib.org...
>> ...
>> >> Calling srand() more than once
>> >> makes sense *only* if you want to repeat the same sequence.
>> >
>> > False.
>> >
>> > 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.'"
>>
>> You are misreading Keith's post. Calling srand multiple times with
>> different seeds during the life time of the program *decreases*
>> the randomness of the sequence generated.
>
> False.
>
> What you are claiming is that the randomness of the sequence
> increases as the rand() function is used.
No, nobody made that claim.
[snip]
> By calling srand() we increased the probability of
> some numbers which had low probability and reduced the probability
> of other numbers which had low probability.
This is nonsense.
So you're asserting that repeatedly calling srand() improves the
randomness of the numbers returned by rand()? In particular, you're
claming that that something like this:
<snip> is likely to yield better (more random) results than if the second
call to srand() were removed (perhaps with a different number of
calls)?
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.
The correct spelling of my name is 'Sinan'.
If you don't comprehend, you can deal with your inabilities in
private.
It is impossible for me to comprehend what you are saying because it
makes no sense. There are a number of standard texts on pseudo RNGs. I
suggest you look them up, and try to find one that recommends constant
reseeding as a way of improving 'randomness'.
"As I've stated previously, the randomness is in the non-perfect
algorithm in rand().
There is no 'the' algorithm in rand(). There are many different
algorithms, and even the simplest ones may differ in the choice of
parameters.
But, the set of numbers generated by rand() is
affected by srand(). srand() doesn't affect the randomness of values
that rand() generates, it only changes the set of generated numbers.
Since the algorithm isn't a perfect-random number generator but a
pseudo-random number generator, the probabilities of certain numbers
occurring is higher than others. These probabilities can be shifted
by calls to srand(). "
But not, in general, in a way that makes the resulting sequence exhibit
desirable properties such as lack of autocorrelation or other patterns.
Consider the simple example:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void re_seed(int seed) {
#ifdef HOSE_ME
srand(seed);
#endif
}
int main(int argc, char *argv[]) {
int i, count;
if ( argc == 1 ) {
count = 1000;
} else {
count = atoi(argv[1]);
}
srand(time(NULL));
for ( i = 0; i < count; ++i ) {
int ri = rand();
re_seed(ri);
printf("%d\n", ri);
}
return 0;
}
/*EOF*/
Compile this program, examine generated sequences. I generated 10
sequences of 100 numbers with HOSE_ME defined, and 10 without.
Then I tested each sequence for autocorrelation. Every sequence with
HOSE_ME defined showed statistically significant autocorrelation at
alpha = 5% where none of the sequences without HOSE_ME defined did.
This is, of course, not a proof, but an example of what we are trying to
get across to you. Both versions of the program were compiled with both
gcc version 3.4.4 and Microsoft (R) 32-bit C/C++ Optimizing Compiler
Version 13.10.3077 for 80x86.
Sinan
--
A. Sinan Unur <1u**@llenroc.ude.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
Rod Pemberton wrote: "Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org... "Rod Pemberton" <do*********@sorry.bitbucket.cmm> writes: "A. Sinan Unur" <1u**@llenroc.ude.invalid> wrote in message
news:Xn****************************@127.0.0.1...
> "Rod Pemberton" <do*********@sorry.bitbucket.cmm> wrote in
> news:dt***********@news3.infoave.net:
> > "Keith Thompson" <ks***@mib.org> wrote in message
> > news:ln************@nuthaus.mib.org...
> ...
> >> Calling srand() more than once
> >> makes sense *only* if you want to repeat the same sequence.
> >
> > False.
> >
> > 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.'"
>
> You are misreading Keith's post. Calling srand multiple times with
> different seeds during the life time of the program *decreases* the
> randomness of the sequence generated.
False.
What you are claiming is that the randomness of the sequence increases as the rand() function is used.
No, nobody made that claim.
[snip]
By calling srand() we increased the probability of some numbers which had low probability and reduced the probability of other numbers which had low probability.
So you're asserting that repeatedly calling srand() improves the
randomness of the numbers returned by rand()? In particular, you're
claming that that something like this:
<snip> is likely to yield better (more random) results than if the second
call to srand() were removed (perhaps with a different number of
calls)?
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.
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.
Since the
algorithm isn't a perfect-random number generator but a pseudo-random number
generator, the probabilities of certain numbers occurring is higher than
others. These probabilities can be shifted by calls to srand(). "
No, they can't. If, starting at state 123456, and you have the
sequence
123456: 123345
123457: 011775
123458: 394875
then that sequence of numbers ALWAYS appears in that order
anytime the sequence finds itself at state 123456. If you start at
state 123456 and generate 1000 PRNs and you then call srand(),
there is a non-zero probability that the state will be set to some
number less than 123456. If it were, say 100 less, then your next
run of 1000 numbers would have a sequence that duplicates the
last 900 numbers of the first block of 1000.
Explain how this is "more random".
Rod Pemberton
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/
Keith Thompson <ks***@mib.org> 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
Keith Thompson wrote: "Rod Pemberton" <do*********@sorry.bitbucket.cmm> writes: "Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.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...) 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...)
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...)
"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_Keith) 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.
Keith Thompson wrote: "Rod Pemberton" <do*********@sorry.bitbucket.cmm> writes: "Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.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...)
Rod Pemberton wrote: "Keith Thompson" <ks***@mib.org> 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/
"Nelu" <ta********@gmail.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_Keith) 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.
On 2006-02-28, Keith Thompson <ks***@mib.org> 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.)
Keith Thompson 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()).
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?
(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_Keith) 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.
Jordan Abel <ra*******@gmail.com> writes: On 2006-02-28, Keith Thompson <ks***@mib.org> wrote:
[...] 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.
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_Keith) 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.
<me********@aol.com> wrote:
Keith Thompson wrote: "me********@aol.com" <me********@aol.com> writes: [...] 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()).
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?
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.
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?
Exactly.
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?
On the long run I can see this too. Imagine a cycle with two different
starting points...
The standard doen't imply that the PRNG must be periodic, does it?
But are there any puely mathematical ones that aren't?
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
Keith Thompson wrote: Jordan Abel <ra*******@gmail.com> writes: On 2006-02-28, Keith Thompson <ks***@mib.org> wrote:
[...] 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.
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).
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
On Mon, 27 Feb 2006 21:19:19 -0800, websnarf wrote: 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.
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.
Other common practical
sources are things like the value of clock() in response to input device
interrupts (like keyboard or mouse inputs.)
<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>
As one final comment -- using the ANSI C's rand() is bad because the
state size is so small
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.
On 2006-02-28, Flash Gordon <sp**@flash-gordon.me.uk> wrote: Keith Thompson wrote: Jordan Abel <ra*******@gmail.com> writes: On 2006-02-28, Keith Thompson <ks***@mib.org> wrote: [...] 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.
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).
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.
If RAND_MAX+1 is a power of 2, it could be done (based on the fact that
a formula exists to independently calculate hex digits of pi)
You'd probably want srand() to initialize the upper bits of the state
[said state would be an index into the "digits" in that case] rather
than the lower ones.
Note that I am *not* an expert on statistics, Pi, or PRNGs.
So basically neither of us knows how good it would really be.
In article <11*********************@t39g2000cwt.googlegroups. com>, me********@aol.com <me********@aol.com> wrote: 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?
Not necessarily.
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?
Not necessarily.
It would be possible to the initial seed to affect parameters
in the PRNG, such that srand(1) and srand(2) each had the same
period, but that the cyles for the two were not the same.
Getting further OT:
It appears to me that the traditional Unix drand48() might be
an instance of this. According to the man page:
The initializer function srand48 sets the high-order 32 bits of Xi
to the 32 bits contained in its argument. The low-order 16 bits of
Xi are set to the arbitrary value 330E16.
and
The value returned by any of the functions drand48, erand48,
lrand48, nrand48, mrand48, or jrand48 is computed by first
generating the next 48-bit Xi in the sequence. Then the
appropriate number of bits, according to the type of data item to
be returned, are copied from the high-order (leftmost) bits of Xi
and transformed into the returned value.
If we put these together, we would see that srand(1) and srand(2)
would have the same cycles -only- if it happened the the linear
congruential generator applied to 0x1330E16 happened to result
in 0x2330E16 at some point. Further analysis would be needed to
see whether that ever happened -- the default multiplier and
constant for drand48() and kin are both even, so it is not
the usual case that "every possible n-bit value will be generated,
eventually".
--
All is vanity. -- Ecclesiastes
On 2006-02-28, Ben Bacarisse <be********@bsb.me.uk> wrote: As one final comment -- using the ANSI C's rand() is bad because the
state size is so small
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.
I think he's referring to the [non-normative] example given in the
standard.
Keith Thompson wrote: "Nelu" <ta********@gmail.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.)
I agree. That's what I was meaning to say starting with 'However' and
the
1 and 2 points :-).
--
Ioan - Ciprian Tandau
tandau _at_ freeshell _dot_ org (hope it's not too late)
(... and that it still works...)
Walter Roberson wrote: In article <11*********************@t39g2000cwt.googlegroups. com>,
me********@aol.com <me********@aol.com> wrote:
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?
Not necessarily.
Then what does "period" mean?
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?
Not necessarily.
Ok.
It would be possible to the initial seed to affect parameters
in the PRNG, such that srand(1) and srand(2) each had the same
period, but that the cyles for the two were not the same.
Ok, but we can't infer that from the standard, can we?
Getting further OT:
It appears to me that the traditional Unix drand48() might be
an instance of this. According to the man page:
The initializer function srand48 sets the high-order 32 bits of Xi
to the 32 bits contained in its argument. The low-order 16 bits of
Xi are set to the arbitrary value 330E16.
Isn't 330E16 24 bits?
and
The value returned by any of the functions drand48, erand48,
lrand48, nrand48, mrand48, or jrand48 is computed by first
generating the next 48-bit Xi in the sequence. Then the
appropriate number of bits, according to the type of data item to
be returned, are copied from the high-order (leftmost) bits of Xi
and transformed into the returned value.
If we put these together, we would see that srand(1) and srand(2)
would have the same cycles -only- if it happened the the linear
congruential generator applied to 0x1330E16 happened to result
in 0x2330E16 at some point. Further analysis would be needed to
see whether that ever happened -- the default multiplier and
constant for drand48() and kin are both even, so it is not
the usual case that "every possible n-bit value will be generated,
eventually".
--
All is vanity. -- Ecclesiastes This thread has been closed and replies have been disabled. Please start a new discussion. |
