Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Generating random seeds for simulation

Reply
Thread Tools

Generating random seeds for simulation

 
 
Intiha
Guest
Posts: n/a
 
      08-25-2006
Hello all,
I am trying to generate random seeds for my simulations.
currently i was using srand(time(NULL); for this purpose.

But for confidence in my results i ran it using a script in a loop.

Since the time b/w execution is very similar, many simulation runs
resulted in exact same results.

Is there a better way of seeding the random number generator in c/c++
than time(NULL).

PS: I did some search and found this small snippet on this group: but i
am not
convinced that it will still result in much different seeds if the
value returned by time(NULL) is the same... any comments?

#include <limits.h>
#include <stdlib.h>
#include <time.h>

void randomize(void)
{
time_t timeval = time(NULL);
unsigned char *ptr = (unsigned char *)&timeval;
unsigned seed = 0;
size_t i;

for (i = 0; i < sizeof timeval; i++)
seed = seed * (UCHAR_MAX+2U) + ptr[i];

srand(seed);

}

 
Reply With Quote
 
 
 
 
Shashank
Guest
Posts: n/a
 
      08-25-2006

I tired many things to avoid the duplications but in vain.
But I have one suggestion for you, use this "timeval" value as seed and
generated the random numbers using this ( i am sure there will not any
duplication) and use the generated random numbers as the seed to your
function.

This may solve your problem.

 
Reply With Quote
 
 
 
 
=?ISO-8859-1?Q?=22Nils_O=2E_Sel=E5sdal=22?=
Guest
Posts: n/a
 
      08-25-2006
Intiha wrote:
> Hello all,
> I am trying to generate random seeds for my simulations.
> currently i was using srand(time(NULL); for this purpose.
>
> But for confidence in my results i ran it using a script in a loop.
>
> Since the time b/w execution is very similar, many simulation runs
> resulted in exact same results.
>
> Is there a better way of seeding the random number generator in c/c++
> than time(NULL).
>
> PS: I did some search and found this small snippet on this group: but i
> am not
> convinced that it will still result in much different seeds if the
> value returned by time(NULL) is the same... any comments?

Som platforms might provide apis for other things that varies
between invocations such as a process id.
Or, if the program is run sequentially, you read a number to
use as a seed from a file at startup, increment it and write it back to
the file.
Other possibilities is to pass part of a seed as an argument, where the
seed is provided by some platform specific way.
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      08-25-2006
Intiha wrote:

> Hello all,
> I am trying to generate random seeds for my simulations.
> currently i was using srand(time(NULL); for this purpose.
>
> But for confidence in my results i ran it using a script in a loop.
>
> Since the time b/w execution is very similar, many simulation runs
> resulted in exact same results.
>
> Is there a better way of seeding the random number generator in c/c++
> than time(NULL).


If you want different outputs, you need different inputs.

In your case, I'd suggest modifying your script so that it
provides a different command-line argument to your program each
time around the loop: "myprog 1", "myprog 2", ... Hash this
value with the time() result so the srand() argument will be
different even if time() doesn't change from one run to the
next. Note that the hash should not be something simple like
`time(NULL) ^ cmdarg', because a small change in time() could
be cancelled by a small change in cmdarg -- do something more
"pervasive," like using cmdarg as the initial value of `seed'
in the randomize() function you quoted.

Some systems provide sources of "truly random" (whatever
that means) numbers, often through a special file name like
/dev/random. These sources are usually slow and hence not a
substitute for rand(), but they provide a good way to get an
srand() argument that's suitably unpredictable. Unfortunately,
such things are not part of C itself, and they way they're
provided (if they're provided) varies from system to system.
Consult your documentation.

Finally, I note that if time() returns the same value at
the start of "many" runs, then your simulation program probably
doesn't run very long. Instead of running the whole program
over and over, struggling with ways to get different srand()
seeds each time, consider rearranging your program so it runs
many simulations each time it executes. Call srand() once at
the beginning of this "super-program," and then just let the
repeated "internal" simulations keep on calling rand().

Old:

int main(void) {
srand(...);
simulate();
return 0;
}

New:

int main(void) {
int run;
srand(...);
for (run = 0; run < 100; ++run)
simulate();
return 0;
}

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid
 
Reply With Quote
 
websnarf@gmail.com
Guest
Posts: n/a
 
      08-25-2006
Intiha wrote:
> I am trying to generate random seeds for my simulations.
> currently i was using srand(time(NULL); for this purpose.
>
> But for confidence in my results i ran it using a script in a loop.
>
> Since the time b/w execution is very similar, many simulation runs
> resulted in exact same results.
>
> Is there a better way of seeding the random number generator in c/c++
> than time(NULL).
>
> PS: I did some search and found this small snippet on this group: but i
> am not
> convinced that it will still result in much different seeds if the
> value returned by time(NULL) is the same... any comments?
>
> #include <limits.h>
> #include <stdlib.h>
> #include <time.h>
>
> void randomize(void)
> {
> time_t timeval = time(NULL);
> unsigned char *ptr = (unsigned char *)&timeval;
> unsigned seed = 0;
> size_t i;
>
> for (i = 0; i < sizeof timeval; i++)
> seed = seed * (UCHAR_MAX+2U) + ptr[i];
>
> srand(seed);
> }


That's not seriously any different from just setting the seed to
time(NULL) in terms of variability. Let's try this:

#include <limits.h>
#include <stdlib.h>
#include <time.h>

static struct {
clock_t c;
time_t t;
int counter;
} entropy = { (clock_t) 0, (time_t) 0, 0 };
static unsigned char * p = (unsigned char *) (&entropy + 1);
static int accSeed = 0;

void randomize (void) {
if (p == ((unsigned char *) (&entropy + 1))) {
entropy.c += clock();
entropy.t += time (NULL);
entropy.counter++;
p = (unsigned char *) &entropy.c;
}
accSeed = ((accSeed * (UCHAR_MAX+2U)) | 1) + (int) *p;
p++;
srand (accSeed);
}

So we are taking 3 sources of entropy, time(NULL), clock() and a simple
incrementing counter. On most 32-bit systems, it will take 12 times
through the randomize() function before it fetches more entropy. Even
if your benchmark takes 0 time, the seed should at least wander through
a pseudo random sequence of numbers, so that you can expect somewhat
different seeding over time.

Obviously you can add platform specific entries to the entropy
structure that reflects more entropic information such as process-ID or
RDTSC on Intel platforms, etc.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

 
Reply With Quote
 
Intiha
Guest
Posts: n/a
 
      08-27-2006
thats one of the ideas that i had. Unfortunately I didnt want to worry
about resetting of the simulation objects before I worried about it.

What i am doing currently (and this certainly fixes the issue as well)
is using a perl scrip to call my program , with the program taking
input a seed.
Now this seed i am generating from the perl scrip that is srand'ed with
time().
This is giving me exactly what you are suggesting without the worry of
simulation clean up (that i know i have to do .. but didnt have time

Thank you All.


Eric Sosman wrote:
> Intiha wrote:
>
> > Hello all,
> > I am trying to generate random seeds for my simulations.
> > currently i was using srand(time(NULL); for this purpose.
> >
> > But for confidence in my results i ran it using a script in a loop.
> >
> > Since the time b/w execution is very similar, many simulation runs
> > resulted in exact same results.
> >
> > Is there a better way of seeding the random number generator in c/c++
> > than time(NULL).

>
> If you want different outputs, you need different inputs.
>
> In your case, I'd suggest modifying your script so that it
> provides a different command-line argument to your program each
> time around the loop: "myprog 1", "myprog 2", ... Hash this
> value with the time() result so the srand() argument will be
> different even if time() doesn't change from one run to the
> next. Note that the hash should not be something simple like
> `time(NULL) ^ cmdarg', because a small change in time() could
> be cancelled by a small change in cmdarg -- do something more
> "pervasive," like using cmdarg as the initial value of `seed'
> in the randomize() function you quoted.
>
> Some systems provide sources of "truly random" (whatever
> that means) numbers, often through a special file name like
> /dev/random. These sources are usually slow and hence not a
> substitute for rand(), but they provide a good way to get an
> srand() argument that's suitably unpredictable. Unfortunately,
> such things are not part of C itself, and they way they're
> provided (if they're provided) varies from system to system.
> Consult your documentation.
>
> Finally, I note that if time() returns the same value at
> the start of "many" runs, then your simulation program probably
> doesn't run very long. Instead of running the whole program
> over and over, struggling with ways to get different srand()
> seeds each time, consider rearranging your program so it runs
> many simulations each time it executes. Call srand() once at
> the beginning of this "super-program," and then just let the
> repeated "internal" simulations keep on calling rand().
>
> Old:
>
> int main(void) {
> srand(...);
> simulate();
> return 0;
> }
>
> New:
>
> int main(void) {
> int run;
> srand(...);
> for (run = 0; run < 100; ++run)
> simulate();
> return 0;
> }
>
> --
> Eric Sosman
> (E-Mail Removed)lid


 
Reply With Quote
 
Dave Thompson
Guest
Posts: n/a
 
      09-04-2006
On 25 Aug 2006 05:41:42 -0700, (E-Mail Removed) wrote:

> Intiha wrote:
> > I am trying to generate random seeds for my simulations.
> > currently i was using srand(time(NULL); for this purpose.
> >
> > But for confidence in my results i ran it using a script in a loop.
> >
> > Since the time b/w execution is very similar, many simulation runs
> > resulted in exact same results.

<snip: hashing value of time()>
> That's not seriously any different from just setting the seed to
> time(NULL) in terms of variability. Let's try this:
>

That's true.

> static struct {
> clock_t c;
> time_t t;
> int counter;
> } entropy = { (clock_t) 0, (time_t) 0, 0 };
> static unsigned char * p = (unsigned char *) (&entropy + 1);
> static int accSeed = 0;
>

Minor point: accSeed doesn't need to be file-scope; it doesn't
remember anything from one call to the next. Even more minor: the
initializers for the struct don't need to be cast and don't even need
to be given at all, although they do provide some documentation and/or
confirmation that you really wanted (needed) the default effect.

> void randomize (void) {
> if (p == ((unsigned char *) (&entropy + 1))) {
> entropy.c += clock();
> entropy.t += time (NULL);
> entropy.counter++;
> p = (unsigned char *) &entropy.c;
> }
> accSeed = ((accSeed * (UCHAR_MAX+2U)) | 1) + (int) *p;
> p++;
> srand (accSeed);
> }
>
> So we are taking 3 sources of entropy, time(NULL), clock() and a simple
> incrementing counter. On most 32-bit systems, it will take 12 times


Not in the situation the OP gave of rerunning the program.
clock() is supposed to reflect the CPU time used _by this execution of
this program_ (i.e. by this process); if called near program startup,
as a randomize function usually should be, it will usually be near
zero. 'counter' is initialized to zero on each program execution and
will always be the same value, 1, on the first call.

> through the randomize() function before it fetches more entropy. Even
> if your benchmark takes 0 time, the seed should at least wander through
> a pseudo random sequence of numbers, so that you can expect somewhat
> different seeding over time.
>
> Obviously you can add platform specific entries to the entropy
> structure that reflects more entropic information such as process-ID or
> RDTSC on Intel platforms, etc.


On most popular OSen for processes run in quick succession, processID
doesn't add _much_ entropy (this was actually partially responsible
for a break of an early implementation of SSL) and a fine(r) clock
like TSC only a modest amount. Although that might have been enough
for the OP, who I see elsethread has instead gone to persisting state
through the invoking script. Another traditional approach in the
program itself is to write out an ending state or value on one run and
read it back it in and use it on the next; this also has the feature
that you can save the seed value(s) if you need (or think you may
need) to recreate some particular run(s).

- David.Thompson1 at worldnet.att.net
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Math.random() and Math.round(Math.random()) and Math.floor(Math.random()*2) VK Javascript 15 05-02-2010 03:43 PM
random.random(), random not defined!? globalrev Python 4 04-20-2008 08:12 AM
How to unit test random seeds? Patricia Shanahan Java 12 12-23-2007 07:14 PM
Doctor Who: The Seeds Of Death DVD Review @ GENRE ONLINE.NET! Writer R5 DVD Video 2 06-23-2004 01:28 AM
larger seeds for Mersenne jt Python 0 02-05-2004 04:41 AM



Advertisments