Portable random number generator

[Gus Gassmann]

I am collaborating on a rather large project with complicated XML
files (some objects nest ten levels deep) and corresponding data
handling challenges. I want to do proper testing of the (C++) code and
decided that the only way to go is random tests. So now I am looking
for a random number generator with the following properties:

1. Portability.
2. Random starting points.
3. Replicability on demand.

I presume this means that I would seed the RNG based on the clock, but
keep a copy of the seed that I could optionally use at the start in
case I found a problem on a previous run.

Statistical properties are of lesser importance.

I presume I am not the first person to attempt this and am hoping to
find some guidance here. Both C and C++ would be OK for the RNG, hence
the cross-post.

Thanks for any hints.

gus

 

[Stefan Ram]

Thanks for any hints.

A »a portable implementation of rand and srand« is published
in ISO/IEC 9899:1999 (E), 7.20.2.2, #5.

 

[Malcolm McLean]

So now I am looking
for a random number generator with the following properties:

1. Portability.
2. Random starting points.
3. Replicability on demand.

Just use the K and R function

static unsigned long random_seed = 123456;

void simplesrand(unsigned long seed)
{
random_seed = seed;
}

int simplerand()
{
random_seed = random_seed * 1103515245 +12345;
return (unsigned int)(random_seed / 65536) % 32768;
}

 

[James Kanze]

I am collaborating on a rather large project with complicated XML
files (some objects nest ten levels deep) and corresponding data
handling challenges. I want to do proper testing of the (C++) code and
decided that the only way to go is random tests. So now I am looking
for a random number generator with the following properties:

1. Portability.
2. Random starting points.
3. Replicability on demand.

I presume this means that I would seed the RNG based on the clock, but
keep a copy of the seed that I could optionally use at the start in
case I found a problem on a previous run.

Statistical properties are of lesser importance.

I presume I am not the first person to attempt this and am hoping to
find some guidance here. Both C and C++ would be OK for the RNG, hence
the cross-post.

There are a number of implementations available on the network;
boost has some, for example. And it's not difficult to
implement the minimum generator yourself.

With regards to the seed: time() is the classical solution, but
depending on the context in which your program runs, it may not
suffice. On Unix platforms, I'll read a couple of bytes from
/dev/random. Otherwise, munging in things like the host IP
address and the process id may be necessary to ensure
uniqueness. (And once you've got a seed, log it so you can use
it in case of problems, like you said.)

 

[Mark Wooding]

So now I am looking for a random number generator with the following
properties:

1. Portability.
2. Random starting points.
3. Replicability on demand.

I presume this means that I would seed the RNG based on the clock, but
keep a copy of the seed that I could optionally use at the start in
case I found a problem on a previous run.

Statistical properties are of lesser importance.

Replicability suggests a determinisic process: random starting points
are then your own problem of choosing a seed in some acceptable way.

There are a number of very simple and fast cryptographic-quality
generators out there (though you don't mention performance as being a
consideration at all).

Rivest's RC4 is extremely simple, and though it has some minor biases
seems adequate for non-cryptographic use if you can tolerate its
octet-at-a-time output.

Bernstein's Salsa20/8 is simple, fast, and seems very secure; it's also
seekable, which may or may not be of interest.

For non-cryptographic applications, I usually use Knuth's lagged
Fibonacci generator, which wants a lot of seed material; for this, I use
a linear congruential generator of my own devising.

I don't have an implementation of Salsa20/8, but you can surely find the
code online; the others are implemented in my Catacomb library, in
(pedantically) portable C:

http://git.distorted.org.uk/~mdw/catacomb/tree

available under the LGPL (see {rc4,fibrand,lc}.[ch]). Since this is for
testing purposes, I imagine the code won't in fact be distributed at all
and LGPL will therefore be acceptable. If I'm wrong about this, send me
mail: I'm willing to be generous with small portions of the library on a
case-by-case basis.

-- [mdw]

 

[Öö Tiib]

I am collaborating on a rather large project with complicated XML
files (some objects nest ten levels deep) and corresponding data
handling challenges. I want to do proper testing of the (C++) code and
decided that the only way to go is random tests. So now I am looking
for a random number generator with the following properties:

1. Portability.
2. Random starting points.
3. Replicability on demand.

I presume this means that I would seed the RNG based on the clock, but
keep a copy of the seed that I could optionally use at the start in
case I found a problem on a previous run.

Statistical properties are of lesser importance.

I presume I am not the first person to attempt this and am hoping to
find some guidance here. Both C and C++ would be OK for the RNG, hence
the cross-post.

Thanks for any hints.

C++0x will contain a clone of boost::random. You can do pretty much
everything with that lib. All generators have their state seedable and
serializable.

Note, that random testing is very powerful tool, but common solution
there is not seedable RNG. Common solution is to automatically
extract exact minimal amount of "steps to reproduce" from noise of
(for example) 300 random operations that resulted with a problem. Then
report/store these as a problem case.

 

[Eric Sosman]

I am collaborating on a rather large project with complicated XML
files (some objects nest ten levels deep) and corresponding data
handling challenges. I want to do proper testing of the (C++) code and
decided that the only way to go is random tests. So now I am looking
for a random number generator with the following properties:

1. Portability.
2. Random starting points.
3. Replicability on demand.

I presume this means that I would seed the RNG based on the clock, but
keep a copy of the seed that I could optionally use at the start in
case I found a problem on a previous run.

Statistical properties are of lesser importance.

I presume I am not the first person to attempt this and am hoping to
find some guidance here. Both C and C++ would be OK for the RNG, hence
the cross-post.

Thanks for any hints.

The C Standard shows a portable example of a way its rand()
function could be implemented; you could take that code, change
the name, file off the serial numbers, and use it.

Depending on what you mean by "replicability," you may or may
not be able to use rand(). On any given system, rand() will be
repeatable: seed it with the same srand() argument, and you'll get
the same sequence of rand() results. But if you need to get the
same sequence on System B that you got earlier on System A, this
mightn't work: A's and B's rand() implementations may differ.
(Some people mistakenly believe that the Standard's example is *the* way
to implement rand(), but it's only an example.) So if you need
agreement across systems, you'll need to incorporate your own code
and not rely on the local rand().

 

[Dag-Erling Smørgrav]

I am collaborating on a rather large project with complicated XML
files (some objects nest ten levels deep) and corresponding data
handling challenges. I want to do proper testing of the (C++) code and
decided that the only way to go is random tests. So now I am looking
for a random number generator with the following properties:

1. Portability.
2. Random starting points.
3. Replicability on demand.

There are plenty of PRNGs (with the P meaning "pseudo", not "portable")
that meet those criteria. Wikipedia is a good starting point,
especially the Mersenne twister article, which includes both pseudocode
and links to existing implementations. IIUC, the Mersenne twister is
currently the best known non-cryptographic deterministic PRNG.

DES

 

[Jeff Flinn]

I am collaborating on a rather large project with complicated XML
files (some objects nest ten levels deep) and corresponding data
handling challenges. I want to do proper testing of the (C++) code and
decided that the only way to go is random tests. So now I am looking
for a random number generator with the following properties:

1. Portability.
2. Random starting points.
3. Replicability on demand.

I'm not sure if all of these are supported, but certainly you should
look at:

http://www.boost.org/doc/libs/1_44_0/doc/html/boost_random.html

Jeff

 

[DDD]

Gus Gassmann ha escrito:

I am collaborating on a rather large project with complicated XML
files (some objects nest ten levels deep) and corresponding data
handling challenges. I want to do proper testing of the (C++) code and
decided that the only way to go is random tests. So now I am looking
for a random number generator with the following properties:

1. Portability.
2. Random starting points.
3. Replicability on demand.

I presume this means that I would seed the RNG based on the clock, but
keep a copy of the seed that I could optionally use at the start in
case I found a problem on a previous run.

Statistical properties are of lesser importance.

I presume I am not the first person to attempt this and am hoping to
find some guidance here. Both C and C++ would be OK for the RNG, hence
the cross-post.

Thanks for any hints.

If there is no exist functions for using, why not writing yourself.
For example, by getting system time in seconds and then...

 

[robertwessel2]

I am collaborating on a rather large project with complicated XML
files (some objects nest ten levels deep) and corresponding data
handling challenges. I want to do proper testing of the (C++) code and
decided that the only way to go is random tests. So now I am looking
for a random number generator with the following properties:

1. Portability.
2. Random starting points.
3. Replicability on demand.

I presume this means that I would seed the RNG based on the clock, but
keep a copy of the seed that I could optionally use at the start in
case I found a problem on a previous run.

Statistical properties are of lesser importance.

I presume I am not the first person to attempt this and am hoping to
find some guidance here. Both C and C++ would be OK for the RNG, hence
the cross-post.

Err... If you don't care much about the quality of the pseudo random
numbers, why not just use the standard srand()/rand()?

 

[robertwessel2]

I am collaborating on a rather large project with complicated XML
files (some objects nest ten levels deep) and corresponding data
handling challenges. I want to do proper testing of the (C++) code and
decided that the only way to go is random tests. So now I am looking
for a random number generator with the following properties:

1. Portability.
2. Random starting points.
3. Replicability on demand.

I presume this means that I would seed the RNG based on the clock, but
keep a copy of the seed that I could optionally use at the start in
case I found a problem on a previous run.

Statistical properties are of lesser importance.

I presume I am not the first person to attempt this and am hoping to
find some guidance here. Both C and C++ would be OK for the RNG, hence
the cross-post.

And if you want a generator that generates the *same* sequences across
platforms, just implement the suggested one from the C standard
(obviously you'll need to change the names):

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;
}

 

[Thomas Richter]

I am collaborating on a rather large project with complicated XML
files (some objects nest ten levels deep) and corresponding data
handling challenges. I want to do proper testing of the (C++) code and
decided that the only way to go is random tests. So now I am looking
for a random number generator with the following properties:

1. Portability.
2. Random starting points.
3. Replicability on demand.

I presume this means that I would seed the RNG based on the clock, but
keep a copy of the seed that I could optionally use at the start in
case I found a problem on a previous run.

Nowadays, stdlib implementations are usually good enough to provide a
suitable random generator under the rand() function. Try that first, it
has the properties you're looking for. This is the "Ford Escort" of
random generators - sufficient for average use.

If not, please come back again.

Greetings,
Thomas

 

[steve]

There are plenty of PRNGs (with the P meaning "pseudo", not "portable")
that meet those criteria.  Wikipedia is a good starting point,
especially the Mersenne twister article, which includes both pseudocode
and links to existing implementations.  IIUC, the Mersenne twister is
currently the best known non-cryptographic deterministic PRNG.

Google Marsaglia or see the c.l.c archive for the last month.

Also, note also that MT has some very undesirable properties.

 

[James Kanze]

On Nov 10, 6:12 am, Gus Gassmann <[email protected]>
wrote:

Just use the K and R function

static unsigned long random_seed = 123456;

void simplesrand(unsigned long seed)
{
random_seed = seed;
}

int simplerand()
{
random_seed = random_seed * 1103515245 +12345;
return (unsigned int)(random_seed / 65536) % 32768;
}

Have you actually tried this one? And done any statistical
analysis on the results?

 

[James Kanze]

On 11/9/2010 11:12 PM, Gus Gassmann wrote:

The C Standard shows a portable example of a way its rand()
function could be implemented; you could take that code,
change the name, file off the serial numbers, and use it.

The "example" random generator in the C standard is particularly
bad.

Depending on what you mean by "replicability," you may or may
not be able to use rand(). On any given system, rand() will be
repeatable: seed it with the same srand() argument, and you'll get
the same sequence of rand() results. But if you need to get the
same sequence on System B that you got earlier on System A, this
mightn't work: A's and B's rand() implementations may differ.
(Some people mistakenly believe that the Standard's example is *the* way
to implement rand(), but it's only an example.)

And in fact, as it is (now) known to be a very poor generator,
none of the implementations I know use it.

So if you need
agreement across systems, you'll need to incorporate your own code
and not rely on the local rand().

You can't rely on the local rand(), but you can easily
incorporate code from Boost or elsewhere, rather than write your
own.

 

[Keith Thompson]

This is not portable (i.e does not generate the same sequence on all
platforms) as the size of unsigned long is platform-depedent. Use
something like uint32_t instead.

Strictly speaking, uint32_t isn't portable. It's new in C99,
so older implementations may not support it (it's likely that
Microsoft doesn't), though you can define it yourself. And it may
not exist at all if the system doesn't happen to support a type
with the required characteristics; for example, I've worked on a
system that had no 32-bit integer type at all.

If you want 100% portability, you can use unsigned long (which
is guaranteed to be *at least* 32 bits) along with some explicit
masking to keep results in the range 0..2**31-1. Or you can use
uint_least32_t if you know you have C99 support.

 

[news]

This is not portable (i.e does not generate the same sequence on all
platforms) as the size of unsigned long is platform-depedent. Use
something like uint32_t instead.

It will only return differing results if unsigned int has less than
31 bits in the target architecture. What are the odds he is going to
use the program in such an environment?

 

[news]

Have you actually tried this one? And done any statistical
analysis on the results?

Since it's a linear congruential generator, there's little need to
do much statistical analysis: It's rather poor.

(Although, admittedly, not all LCG's are equally poor. Some are way
poorer than others, if the literals are chosen inappropriately. However,
even the best LCG's are rather poor compared to more robust RNG's.)

 

[lawrence.jones]

The "example" random generator in the C standard is particularly
bad. [...]
And in fact, as it is (now) known to be a very poor generator,
none of the implementations I know use it.

No, it's not. It's a perfectly good 15-bit linear congruential
generator. Certainly there are other forms of generators that are
"better" by some measures, but as LCGs go, it's a decent one. A number
of implementations use it verbatim.