Pseudorandom algorithms

Discussion in 'C Programming' started by Tatu Portin, Dec 21, 2005.

  1. Tatu Portin

    Tatu Portin Guest

    I need a pseudorandom algorithm that produces same results with same
    seed across different platforms. I'm not sure, but I think that
    standard rand() does produce different set of numbers on different
    platforms. I would be using only four distinct values,
    i.e. (rand() % 4).

    This algorithm would be used to generate a bitmap when a game starts,
    and if randomness is platform-variable, the game will look different
    on different platforms and this is not what I want.


    --
    C faq: http://www.eskimo.com/~scs/C-faq/top.html
    Reference: http://www.acm.uiuc.edu/webmonkeys/book/c_guide/
    Coding standards: http://www.psgd.org/paul/docs/cstyle/cstyle.htm
    Tatu Portin, Dec 21, 2005
    #1
    1. Advertising

  2. Tatu Portin

    Michael Mair Guest

    Tatu Portin wrote:
    > I need a pseudorandom algorithm that produces same results with same
    > seed across different platforms. I'm not sure, but I think that
    > standard rand() does produce different set of numbers on different
    > platforms. I would be using only four distinct values,
    > i.e. (rand() % 4).
    >
    > This algorithm would be used to generate a bitmap when a game starts,
    > and if randomness is platform-variable, the game will look different
    > on different platforms and this is not what I want.


    The standard does not prescribe much w.r.t. rand().
    So, if you need a pseudorandom number generator which behaves
    identically for identical seeds througout different platforms,
    write one yourself. Take into account that integer type widths
    may vary.

    Cheers
    Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
    Michael Mair, Dec 21, 2005
    #2
    1. Advertising

  3. Tatu Portin <> writes:
    > I need a pseudorandom algorithm that produces same results with same
    > seed across different platforms. I'm not sure, but I think that
    > standard rand() does produce different set of numbers on different
    > platforms. I would be using only four distinct values,
    > i.e. (rand() % 4).
    >
    > This algorithm would be used to generate a bitmap when a game starts,
    > and if randomness is platform-variable, the game will look different
    > on different platforms and this is not what I want.


    Right, there's no requirement for all C implementations to use the
    same algorithm, but there is a sample algorithm in the standard.
    C99 7.20.2.2:

    static unsigned long int next = 1;

    int rand(void) // RAND_MAX assumed to be 32767
    {
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
    }

    void srand(unsigned int seed)
    {
    next = seed;
    }

    If you change the names of the functions (so they don't conflict with
    the standard functions), I *think* the above code will give you the
    same sequence for the same seed on all platforms. (Don't take my word
    for that; try it on all platforms you're interested in.)

    --
    Keith Thompson (The_Other_Keith) <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, Dec 21, 2005
    #3
  4. Tatu Portin

    Tim Rentsch Guest

    Tatu Portin <> writes:

    > I need a pseudorandom algorithm that produces same results with same
    > seed across different platforms. I'm not sure, but I think that
    > standard rand() does produce different set of numbers on different
    > platforms. I would be using only four distinct values,
    > i.e. (rand() % 4).
    >
    > This algorithm would be used to generate a bitmap when a game starts,
    > and if randomness is platform-variable, the game will look different
    > on different platforms and this is not what I want.


    /***** This file is prand32.h *****/
    #ifndef H_PRAND32_H
    #define H_PRAND32_H

    /**************************************************************************/
    /* A portable, platform independent, pseudo-random number generator. */
    /* */
    /* random_32() yields a 32-bit, uniformly distributed, "random number". */
    /* */
    /* Use seed_random_32() to supply a 32-bit seed value for random_32(). */
    /**************************************************************************/


    #define random_32() (*--random_32_p ? *random_32_p : cycle_random_32())

    extern void seed_random_32( unsigned long );
    extern unsigned long (random_32)( void );


    /*************************/
    /* for internal use only */
    /*************************/
    extern unsigned long cycle_random_32( void );
    extern const unsigned long *random_32_p;


    #endif /* H_PRAND_H */
    /***** End of prand32.h *****/




    /***** This file is prand32.c *****/
    #include "prand32.h"


    /***********************************************************/
    /* The method employed is based on a lagged fibonacci PRNG */
    /* given in Knuth's "Graph Base" book. */
    /***********************************************************/

    #define VALUES_N (55u)
    #define VALUES_D (24u)
    /* Other reasonable values: 33,20 17,11 9,5 */


    #define VALUES_INDEX_LIMIT (VALUES_N + 1)

    static unsigned long values[VALUES_INDEX_LIMIT];
    const unsigned long *random_32_p = values + VALUES_INDEX_LIMIT;
    static const unsigned long mask32 = 0xffffffffUL;


    void
    seed_random_32( unsigned long seed_value ){
    unsigned i;

    values[1] = seed_value & mask32;
    for( i = 2; i < VALUES_INDEX_LIMIT; i++ ) values = 0;

    for( i = 0; i < VALUES_INDEX_LIMIT * 2; i++ ){
    random_32_p = &values[0];
    (void) cycle_random_32();
    }
    }


    unsigned long
    (random_32)( void ){
    return random_32();
    }


    unsigned long
    cycle_random_32(){
    unsigned i;

    if( random_32_p == &values[0] ){
    for( i = 1; i + VALUES_D < VALUES_INDEX_LIMIT; i++ ){
    values -= values[ i+VALUES_D ];
    values &= mask32;
    }
    for( i = i; i < VALUES_INDEX_LIMIT; i++ ){
    values -= values[ i - (VALUES_N - VALUES_D) ];
    values &= mask32;
    }

    for( i = 1; i < VALUES_INDEX_LIMIT; i++ ){
    values ^= (mask32 ^ values[i-1]) >> 1;
    }

    random_32_p = &values[VALUES_INDEX_LIMIT - 1];

    } else if( random_32_p == &values[VALUES_INDEX_LIMIT - 1] ){
    seed_random_32( 0 );
    }

    return *random_32_p;
    }

    /***** End of prand32.c *****/


    Query to comp.lang.c readers: What platform dependencies
    did I miss?
    Tim Rentsch, Dec 29, 2005
    #4
  5. Tatu Portin

    Guest

    Keith Thompson schreef:

    > Tatu Portin <> writes:
    > > I need a pseudorandom algorithm that produces same results with same
    > > seed across different platforms. I'm not sure, but I think that
    > > standard rand() does produce different set of numbers on different
    > > platforms. I would be using only four distinct values,
    > > i.e. (rand() % 4).
    > >
    > > This algorithm would be used to generate a bitmap when a game starts,
    > > and if randomness is platform-variable, the game will look different
    > > on different platforms and this is not what I want.

    >
    > Right, there's no requirement for all C implementations to use the
    > same algorithm, but there is a sample algorithm in the standard.
    > C99 7.20.2.2:
    >
    > static unsigned long int next = 1;
    >
    > int rand(void) // RAND_MAX assumed to be 32767
    > {
    > next = next * 1103515245 + 12345;
    > return (unsigned int)(next/65536) % 32768;
    > }
    >
    > void srand(unsigned int seed)
    > {
    > next = seed;
    > }
    >
    > If you change the names of the functions (so they don't conflict with
    > the standard functions), I *think* the above code will give you the
    > same sequence for the same seed on all platforms. (Don't take my word
    > for that; try it on all platforms you're interested in.)


    Assuming all have a 32-bit int (or bigger) and there aren't any bugs in
    basic arithmatic instructions, i don't really see how the results
    _could_ differ. After all, it's fairly basic math and I totally fail to
    spot any possible implementation or platform dependencies.

    However, as Dr. Knuth wrote: "be wary of bugs in the above code. I've
    only proven it correct, not actually tried it."
    , Dec 29, 2005
    #5
    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. Andreas
    Replies:
    0
    Views:
    507
    Andreas
    Dec 2, 2003
  2. abhinav

    encryption algorithms

    abhinav, Dec 26, 2004, in forum: VHDL
    Replies:
    2
    Views:
    642
  3. Melanie Nasic
    Replies:
    19
    Views:
    3,030
    Thomas Rudloff
    Jan 1, 2006
  4. Soenke
    Replies:
    0
    Views:
    561
    Soenke
    Dec 28, 2005
  5. comp.lang.vhdl

    Pseudorandom Noise Generator....

    comp.lang.vhdl, Mar 16, 2009, in forum: VHDL
    Replies:
    2
    Views:
    995
    JohnDuq
    Mar 18, 2009
Loading...

Share This Page