Random number generator.

[jason.cipriani]

I am looking for a random number generator implementation with the
following requirements:

- Thread-safe, re-entrant.
- Produces consistently reproducible sequences of psuedo-random
numbers given a seed.
- Relatively uniform, does not have to be perfect.

The application is not a security or statistics application, the
quality of numbers is not a priority although a fairly uniform
distribution would be nice. The application I am using it for is
generating random numbers for controlling audio and video effects, and
the user must be able to specify a seed to produce the same sequence
of "random" numbers every time. However, there may be many such
"streams" of random numbers being generated at the same time, each
which is seeded with it's own starting value and must produce
sequences independent of every other "stream".

This is a minor feature I want to add to my application (which is just
using rand() with no predictability right now). Therefore, to be
honest, I am not interested in doing any major amount of work or
research. I am wondering if anybody knows of a decent implementation
that is easy to drop in to existing code (there doesn't appear to be
anything in the STL, is there?).

Thanks,
Jason

 

[Erik Wikström]

I am looking for a random number generator implementation with the
following requirements:

- Thread-safe, re-entrant.
- Produces consistently reproducible sequences of psuedo-random
numbers given a seed.
- Relatively uniform, does not have to be perfect.

The application is not a security or statistics application, the
quality of numbers is not a priority although a fairly uniform
distribution would be nice. The application I am using it for is
generating random numbers for controlling audio and video effects, and
the user must be able to specify a seed to produce the same sequence
of "random" numbers every time. However, there may be many such
"streams" of random numbers being generated at the same time, each
which is seeded with it's own starting value and must produce
sequences independent of every other "stream".

This is a minor feature I want to add to my application (which is just
using rand() with no predictability right now). Therefore, to be
honest, I am not interested in doing any major amount of work or
research. I am wondering if anybody knows of a decent implementation
that is easy to drop in to existing code (there doesn't appear to be
anything in the STL, is there?).

I do not know about the uniformity, but using srand() and calling it
with the last generated number (of a function thereof) should make it
re-entrant.

 

[jason.cipriani]

I do not know about the uniformity, but using srand() and calling it
with the last generated number (of a function thereof) should make it
re-entrant.

Thanks, I guess that is a pretty obvious solution. So something like
this:

class RandomNumber {
public:
RandomNumber (int seed) : seed_(seed) { }
void Seed (int seed) { seed_ = seed; }
int Next () { srand(seed_); return rand(); }
private:
int seed_;
};

My question there is, is rand() guaranteed to give the same sequence
of numbers given a seed on every platform and every machine, for every
standard library implementation? My particular application does run on
many platforms and many computers, and the user will expect to see the
exact same results on every machine given the same inputs.

Thanks,
Jason

 

[jason.cipriani]

class RandomNumber {
public:
RandomNumber (int seed) : seed_(seed) { }
void Seed (int seed) { seed_ = seed; }
int Next () { srand(seed_); return rand(); }
private:
int seed_;
};

Oops. That should, of course, be:

int Next () {
srand(seed_);
seed_ = rand(); // <----
return seed_;
}

 

[Erik Wikström]

Thanks, I guess that is a pretty obvious solution. So something like
this:

class RandomNumber {
public:
RandomNumber (int seed) : seed_(seed) { }
void Seed (int seed) { seed_ = seed; }
int Next () { srand(seed_); return rand(); }
private:
int seed_;
};

My question there is, is rand() guaranteed to give the same sequence
of numbers given a seed on every platform and every machine, for every
standard library implementation? My particular application does run on
many platforms and many computers, and the user will expect to see the
exact same results on every machine given the same inputs.

No, if you need consistency on many different platforms you need to get
some other function. The wikipedia article about linear congruential
generators gives an algorithm you can use. Or you can google for pseudo
random number generators, there should be a few libraries available.

 

[Darío Griffo]

This is a minor feature I want to add to my application (which is just
using rand() with no predictability right now). Therefore, to be
honest, I am not interested in doing any major amount of work or
research. I am wondering if anybody knows of a decent implementation
that is easy to drop in to existing code (there doesn't appear to be
anything in the STL, is there?).

Thanks,
Jason

From man 3 rand

POSIX.1-2001 gives the following example of an implementation of
rand() and srand(), possibly useful when one needs the same sequence
on two different machines.


static unsigned long next = 1;

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

void mysrand(unsigned seed) {
next = seed;
}

 

[Kai-Uwe Bux]

I am looking for a random number generator implementation with the
following requirements:

- Thread-safe, re-entrant.
- Produces consistently reproducible sequences of psuedo-random
numbers given a seed.
- Relatively uniform, does not have to be perfect.

The application is not a security or statistics application, the
quality of numbers is not a priority although a fairly uniform
distribution would be nice. The application I am using it for is
generating random numbers for controlling audio and video effects, and
the user must be able to specify a seed to produce the same sequence
of "random" numbers every time. However, there may be many such
"streams" of random numbers being generated at the same time, each
which is seeded with it's own starting value and must produce
sequences independent of every other "stream".

This is a minor feature I want to add to my application (which is just
using rand() with no predictability right now). Therefore, to be
honest, I am not interested in doing any major amount of work or
research. I am wondering if anybody knows of a decent implementation
that is easy to drop in to existing code (there doesn't appear to be
anything in the STL, is there?).

Assuming that your compiler supports 64 bit long long types, you could use
this simple linear congruence RNG, which has reasonable properties:


// Line26.cc
// =========
/*
Implementing a variation of the RNG from
Table 1 [TAOCP, 3.3.4], line 26.
*/

#ifndef KUBUX_LINE26
#define KUBUX_LINE26

namespace kubux {

class Line26 {

unsigned long long state;

static const unsigned long long a =
6364136223846793005ull; // cong 5 mod 8

static const unsigned long long c =
314159ull; // odd

public:

Line26 ( unsigned long seed = 0 )
: state ( 126871263818671ull + a * seed )
{}

unsigned long min ( void ) const {
return ( 0 );
}

unsigned long max ( void ) const {
return ( 0xfffffffful );
}

unsigned long operator() ( void ) {
state = state * a + c & 0xffffffffffffffffull;
return ( state >> 32 );
}

unsigned long operator() ( unsigned long n ) {
unsigned long long bucket_size =
}

};

} // kubux

#endif

// end of file

#include <iostream>
#include <iomanip>

int main ( void ) {
kubux::Line26 rng;
while ( true ) {
std::cout << std::hex << rng() << '\n';
}
}


Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

Oops. That should, of course, be:

int Next () {
srand(seed_);
seed_ = rand(); // <----
return seed_;
}

Bad idea: that will limit the period to at most RAND_MAX+1. Moreover, you
loose all the theory behind the implementation of rand(), which probably
exists even although it might not be documented. In particular, you could
end up with something that is not even uniform.


Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

Assuming that your compiler supports 64 bit long long types, you could use
this simple linear congruence RNG, which has reasonable properties:

[oops: missed the body of operator()( bound )]

// Line26.cc (C) Kai-Uwe Bux [2008]
// ================================
/*
Implementing a variation of the RNG from
Table 1 [TAOCP, 3.3.4], line 26.
*/

#ifndef KUBUX_LINE26
#define KUBUX_LINE26

namespace kubux {

class Line26 {

unsigned long long state;

static const unsigned long long a =
6364136223846793005ull; // cong 5 mod 8

static const unsigned long long c =
314159ull; // odd

public:

Line26 ( unsigned long seed = 0 )
: state ( 126871263818671ull + a * seed )
{}

unsigned long min ( void ) const {
return ( 0 );
}

unsigned long max ( void ) const {
return ( 0xfffffffful );
}

unsigned long operator() ( void ) {
state = state * a + c & 0xffffffffffffffffull;
return ( state >> 32 );
}

unsigned long operator() ( unsigned long n ) {
unsigned long long bucket_size = (unsigned long long)(-1) / n;
unsigned long long past_valid = bucket_size * n;
do {
state = state * a + c & 0xffffffffffffffffull;
} while ( state >= past_valid );
return ( state / bucket_size );
}

};

} // kubux

#endif

// end of file

#include <iostream>
#include <iomanip>

int main ( void ) {
kubux::Line26 rng;
while ( true ) {
std::cout << rng(10u) << '\n';
}
}


Best

Kai-Uwe Bux

 

[Jerry Coffin]

I am looking for a random number generator implementation with the
following requirements:

- Thread-safe, re-entrant.
- Produces consistently reproducible sequences of psuedo-random
numbers given a seed.
- Relatively uniform, does not have to be perfect.

TR1 has a <random> header containing some templates for random number
generation. C++ 0x also contains some random number generation
templates. While most of TR1 was adopted into C++ 0x with little or no
change, IIRC, the part dealing with random number generation was
extensively modified.

 

[kalman]

I am looking for a random number generator implementation with the
following requirements:

 - Thread-safe, re-entrant.
 - Produces consistently reproducible sequences of psuedo-random
numbers given a seed.
 - Relatively uniform, does not have to be perfect.

The application is not a security or statistics application, the
quality of numbers is not a priority although a fairly uniform
distribution would be nice. The application I am using it for is
generating random numbers for controlling audio and video effects, and
the user must be able to specify a seed to produce the same sequence
of "random" numbers every time. However, there may be many such
"streams" of random numbers being generated at the same time, each
which is seeded with it's own starting value and must produce
sequences independent of every other "stream".

This is a minor feature I want to add to my application (which is just
using rand() with no predictability right now). Therefore, to be
honest, I am not interested in doing any major amount of work or
research. I am wondering if anybody knows of a decent implementation
that is easy to drop in to existing code (there doesn't appear to be
anything in the STL, is there?).

Thanks,
Jason

Why don't you just use the boost generator one ?
You can find more info here:

http://www.boost.org/doc/libs/1_35_0/libs/random/random-generators.html

 

[James Kanze]

From man 3 rand

POSIX.1-2001 gives the following example of an implementation of
rand() and srand(), possibly useful when one needs the same sequence
on two different machines.

static unsigned long next = 1;

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

void mysrand(unsigned seed) {
next = seed;
}

Posix just copied this from the C standard. It's known to be
very poor.

If you're interested in linear congruent generators, you should
at least read "Random Number Generators: Good Ones Are Hard to
Find", by Park and Miller (CACM, Oct. 1988). If you want
portable repeatability, then you can just use the generator they
suggest. I've corrected some of the known weaknesses in this
generator (and significantly extended its period) in my own
Random class (available at my site), and Boost has a large
collection of fully specified random generators, some with
characteristics far better than mine. To be frank, I'd
recommend using one of the Boost generators rather than my own.

 

[bilgekhan]

Assuming that your compiler supports 64 bit long long types, you could use
this simple linear congruence RNG, which has reasonable properties:

[oops: missed the body of operator()( bound )]

// Line26.cc (C) Kai-Uwe Bux [2008]
// ================================
/*
Implementing a variation of the RNG from
Table 1 [TAOCP, 3.3.4], line 26.
*/

#ifndef KUBUX_LINE26
#define KUBUX_LINE26

namespace kubux {

class Line26 {

unsigned long long state;

static const unsigned long long a =
6364136223846793005ull; // cong 5 mod 8

static const unsigned long long c =
314159ull; // odd

public:

Line26 ( unsigned long seed = 0 )
: state ( 126871263818671ull + a * seed )
{}

unsigned long min ( void ) const {
return ( 0 );
}

unsigned long max ( void ) const {
return ( 0xfffffffful );
}

unsigned long operator() ( void ) {
state = state * a + c & 0xffffffffffffffffull;
return ( state >> 32 );
}

unsigned long operator() ( unsigned long n ) {
unsigned long long bucket_size = (unsigned long long)(-1) / n;
unsigned long long past_valid = bucket_size * n;
do {
state = state * a + c & 0xffffffffffffffffull;
} while ( state >= past_valid );
return ( state / bucket_size );
}

};

} // kubux

#endif

// end of file

#include <iostream>
#include <iomanip>

int main ( void ) {
kubux::Line26 rng;
while ( true ) {
std::cout << rng(10u) << '\n';
}
}

Hi Kai-Uwe,
what are the specifications of the above generator?
(ie. its RAND_MAX and period)
Is it true that linear congruential RNGs generate
each number only once during a period?
That they can be used to efficiently random walk
an array that has a certain length? Ie. visiting each
element only once, and doing that in random order.

 

[Kai-Uwe Bux]

(e-mail address removed) wrote:

I am looking for a random number generator implementation with the
following requirements:

- Thread-safe, re-entrant.
- Produces consistently reproducible sequences of psuedo-random
numbers given a seed.
- Relatively uniform, does not have to be perfect.

The application is not a security or statistics application, the
quality of numbers is not a priority although a fairly uniform
distribution would be nice. The application I am using it for is
generating random numbers for controlling audio and video effects, and
the user must be able to specify a seed to produce the same sequence
of "random" numbers every time. However, there may be many such
"streams" of random numbers being generated at the same time, each
which is seeded with it's own starting value and must produce
sequences independent of every other "stream".

This is a minor feature I want to add to my application (which is just
using rand() with no predictability right now). Therefore, to be
honest, I am not interested in doing any major amount of work or
research. I am wondering if anybody knows of a decent implementation
that is easy to drop in to existing code (there doesn't appear to be
anything in the STL, is there?).

Assuming that your compiler supports 64 bit long long types, you could
use this simple linear congruence RNG, which has reasonable properties:

[oops: missed the body of operator()( bound )]

// Line26.cc (C) Kai-Uwe Bux [2008]
// ================================
/*
Implementing a variation of the RNG from
Table 1 [TAOCP, 3.3.4], line 26.
*/

#ifndef KUBUX_LINE26
#define KUBUX_LINE26

namespace kubux {

class Line26 {

unsigned long long state;

static const unsigned long long a =
6364136223846793005ull; // cong 5 mod 8

static const unsigned long long c =
314159ull; // odd

public:

Line26 ( unsigned long seed = 0 )
: state ( 126871263818671ull + a * seed )
{}

unsigned long min ( void ) const {
return ( 0 );
}

unsigned long max ( void ) const {
return ( 0xfffffffful );
}

unsigned long operator() ( void ) {
state = state * a + c & 0xffffffffffffffffull;
return ( state >> 32 );
}

unsigned long operator() ( unsigned long n ) {
unsigned long long bucket_size = (unsigned long long)(-1) / n;
unsigned long long past_valid = bucket_size * n;
do {
state = state * a + c & 0xffffffffffffffffull;
} while ( state >= past_valid );
return ( state / bucket_size );
}

};

} // kubux

#endif

// end of file

#include <iostream>
#include <iomanip>

int main ( void ) {
kubux::Line26 rng;
while ( true ) {
std::cout << rng(10u) << '\n';
}
}

Hi Kai-Uwe,
what are the specifications of the above generator?
(ie. its RAND_MAX and period)

The RAND_MAX is what max() returns: 2^32-1.

Is it true that linear congruential RNGs generate
each number only once during a period?

Yes.

However, the above is nor a pure linear congruential RNG. It masks the
lowest 32 bits of the internal state before output. The period of the above
is 2^64. More precisely, the period of the lowest order bit is 2^33, and
the period of the highest order bit is 2^64. This is good enough for most
purposes.

More importantly, the above RNG has good spectral properties as shown in
Knuth's table.

That they can be used to efficiently random walk
an array that has a certain length? Ie. visiting each
element only once, and doing that in random order.

Given the recursion

x := a*x+c % m

the best that can happen is that x traverses the numbers in [0,m) in some
order. However, for many possible triples (m,a,c), not all numbers will be
visited. The above is chosen so that the internal state has a full period.


Best

Kai-Uwe Bux

 

[Juha Nieminen]

- Thread-safe, re-entrant.
- Produces consistently reproducible sequences of psuedo-random
numbers given a seed.

I find those a bit contradictory.

If you are going to use the *same* RNG instance in more than one
thread *at the same time*, you cannot hope to always get the same number
sequence from it (because some other thread might pull a number from the
RNG while the first thread is getting a number sequence from it).

I assume that you want each thread to have its own independent RNG
instance which cannot be messed up by other threads (so that you can
consistently get the same sequences with a given seed). If that's the
case then the RNG doesn't have to be thread-safe (because only one
thread is accessing it anyways). The only requirement is that you can
create independent instances of that RNG.

Here's a high-quality very fast RNG class:

http://warp.povusers.org/IsaacRand.zip