Velocity Reviews > Pseudorandom algorithms

# Pseudorandom algorithms

Tatu Portin
Guest
Posts: n/a

 12-21-2005
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
Guest
Posts: n/a

 12-21-2005
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
Guest
Posts: n/a

 12-21-2005
Tatu Portin <(E-Mail Removed)> 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.velocityreviews.com/forums/(E-Mail Removed) <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
Guest
Posts: n/a

 12-29-2005
Tatu Portin <(E-Mail Removed)> 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;

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 ];
}
for( i = i; i < VALUES_INDEX_LIMIT; i++ ){
values[i] -= values[ i - (VALUES_N - VALUES_D) ];
}

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@xs4all.nl
Guest
Posts: n/a

 12-29-2005

Keith Thompson schreef:

> Tatu Portin <(E-Mail Removed)> 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."