Generating random seeds for simulation

Discussion in 'C Programming' started by Intiha, Aug 25, 2006.

  1. Intiha

    Intiha Guest

    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;

    srand(seed);

    }
    Intiha, Aug 25, 2006
    #1
    1. Advertising

  2. Intiha

    Shashank Guest

    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.
    Shashank, Aug 25, 2006
    #2
    1. Advertising

  3. 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.
    =?ISO-8859-1?Q?=22Nils_O=2E_Sel=E5sdal=22?=, Aug 25, 2006
    #3
  4. Intiha

    Eric Sosman Guest

    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
    lid
    Eric Sosman, Aug 25, 2006
    #4
  5. Intiha

    Guest

    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;
    >
    > 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/
    , Aug 25, 2006
    #5
  6. Intiha

    Intiha Guest

    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
    > lid
    Intiha, Aug 27, 2006
    #6
  7. On 25 Aug 2006 05:41:42 -0700, 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
    Dave Thompson, Sep 4, 2006
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jt

    larger seeds for Mersenne

    jt, Feb 5, 2004, in forum: Python
    Replies:
    0
    Views:
    327
  2. jt

    larger seeds for Mersenne

    jt, Feb 6, 2004, in forum: Python
    Replies:
    0
    Views:
    323
  3. Patricia Shanahan

    How to unit test random seeds?

    Patricia Shanahan, Dec 20, 2007, in forum: Java
    Replies:
    12
    Views:
    839
    Patricia Shanahan
    Dec 23, 2007
  4. globalrev
    Replies:
    4
    Views:
    753
    Gabriel Genellina
    Apr 20, 2008
  5. Replies:
    4
    Views:
    271
Loading...

Share This Page