Pseudorandom algorithms

[Tatu Portin]

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

[Michael Mair]

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.

[Keith Thompson]

Tatu Portin <ax****@mbnet.fi> 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) 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.

[Tim Rentsch]

Tatu Portin <ax****@mbnet.fi> 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[i] = 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[i] -= values[ i+VALUES_D ];
values[i] &= mask32;
}
for( i = i; i < VALUES_INDEX_LIMIT; i++ ){
values[i] -= values[ i - (VALUES_N - VALUES_D) ];
values[i] &= mask32;
}

for( i = 1; i < VALUES_INDEX_LIMIT; i++ ){
values[i] ^= (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?

[kleuske]

Keith Thompson schreef:

Tatu Portin <ax****@mbnet.fi> 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."