By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,314 Members | 2,155 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,314 IT Pros & Developers. It's quick & easy.

Random number generator.

P: n/a
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
Jun 27 '08 #1
Share this Question
Share on Google+
14 Replies


P: n/a
On 2008-05-31 19:09, ja************@gmail.com 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?).
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.

--
Erik Wikström
Jun 27 '08 #2

P: n/a
On May 31, 1:30 pm, Erik Wikström <Erik-wikst...@telia.comwrote:
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
Jun 27 '08 #3

P: n/a
On May 31, 1:37 pm, "jason.cipri...@gmail.com"
<jason.cipri...@gmail.comwrote:
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_;
}

Jun 27 '08 #4

P: n/a
On 2008-05-31 19:37, ja************@gmail.com wrote:
On May 31, 1:30 pm, Erik Wikström <Erik-wikst...@telia.comwrote:
>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.
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.

--
Erik Wikström
Jun 27 '08 #5

P: n/a
On May 31, 2:09 pm, "jason.cipri...@gmail.com"
<jason.cipri...@gmail.comwrote:
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;
}
Jun 27 '08 #6

P: n/a
ja************@gmail.com 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:
// 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

Jun 27 '08 #7

P: n/a
ja************@gmail.com wrote:
On May 31, 1:37 pm, "jason.cipri...@gmail.com"
<jason.cipri...@gmail.comwrote:
>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_;
}
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
Jun 27 '08 #8

P: n/a
Kai-Uwe Bux wrote:
ja************@gmail.com 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';
}
}
Best

Kai-Uwe Bux
Jun 27 '08 #9

P: n/a
In article <f7fdf24f-cf85-42a2-aa7d-3cd2eb9c891b@
34g2000hsf.googlegroups.com>, ja************@gmail.com says...
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 <randomheader 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.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jun 27 '08 #10

P: n/a
On May 31, 7:09*pm, "jason.cipri...@gmail.com"
<jason.cipri...@gmail.comwrote:
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...enerators.html
Jun 27 '08 #11

P: n/a
Sam
ja************@gmail.com writes:
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.
These two requirements are mutually exclusive, unless you have very, very
precise control over multiple threads' invocation of your random number
generation function.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEABECAAYFAkhBqKUACgkQx9p3GYHlUOI7OgCdEU8Gs4v2Q+ Iprd27F/VunZL/
dZ0An3CNfoCeLhA+cELzDRowwAmcB2xh
=e+k7
-----END PGP SIGNATURE-----

Jun 27 '08 #12

P: n/a
On 2008-05-31 15:36:05 -0400, Sam <sa*@email-scan.comsaid:
This is a MIME GnuPG-signed message. If you see this text, it means that
your E-mail or Usenet software does not support MIME signed messages.
The Internet standard for MIME PGP messages, RFC 2015, was published in 1996.
To open this message correctly you will need to install E-mail or Usenet
software that supports modern Internet standards.

--=_mimegpg-commodore.email-scan.com-5848-1212262565-0002
Content-Type: text/plain; format=flowed; charset="US-ASCII"
Content-Disposition: inline
Content-Transfer-Encoding: 7bit

ja************@gmail.com writes:
>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.

These two requirements are mutually exclusive, unless you have very, very
precise control over multiple threads' invocation of your random number
generation function.
Well, yes and no. Read literally, yes. In fact, no problem: write a
generator type that holds its state in an object, and use one object
per thread. That's one of the key ideas in the TR1/C++0x random number
generators.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Jun 27 '08 #13

P: n/a
On May 31, 8:00 pm, Darío Griffo <dario.griffo.lis...@gmail.com>
wrote:
On May 31, 2:09 pm, "jason.cipri...@gmail.com"
<jason.cipri...@gmail.comwrote:
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?).
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.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Jun 27 '08 #14

P: n/a
ja************@gmail.com wrote:
- 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
Jun 27 '08 #15

This discussion thread is closed

Replies have been disabled for this discussion.