Random number generator.

[jason.cipriani@gmail.com]

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

[=?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=]

Re: Random number generator.

On 2008-05-31 19:09, jason.cipriani@ 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

[jason.cipriani@gmail.com]

Re: Random number generator.

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

[jason.cipriani@gmail.com]

Re: Random number generator.

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

[=?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=]

Re: Random number generator.

On 2008-05-31 19:37, jason.cipriani@ 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

[=?ISO-8859-1?Q?Dar=EDo_Griffo?=]

Re: Random number generator.

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((unsigne d)(next/65536) % 32768);
}

void mysrand(unsigne d seed) {
next = seed;
}

[Kai-Uwe Bux]

Re: Random number generator.

jason.cipriani@ 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 =
636413622384679 3005ull; // cong 5 mod 8

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

public:

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

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

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

unsigned long operator() ( void ) {
state = state * a + c & 0xfffffffffffff fffull;
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]

Re: Random number generator.

jason.cipriani@ 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

[Kai-Uwe Bux]

Re: Random number generator.

Kai-Uwe Bux wrote:

jason.cipriani@ 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 =
636413622384679 3005ull; // cong 5 mod 8

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

public:

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

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

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

unsigned long operator() ( void ) {
state = state * a + c & 0xfffffffffffff fffull;
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 & 0xfffffffffffff fffull;
} 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]

Re: Random number generator.

In article <f7fdf24f-cf85-42a2-aa7d-3cd2eb9c891b@
34g2000hsf.goog legroups.com>, jason.cipriani@ 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.

[kalman]

Re: Random number generator.

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/libs/random/random-generators.html

[Sam]

Re: Random number generator.

jason.cipriani@ 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)

iEYEABECAAYFAkh BqKUACgkQx9p3GY HlUOI7OgCdEU8Gs 4v2Q+Iprd27F/VunZL/
dZ0An3CNfoCeLhA +cELzDRowwAmcB2 xh
=e+k7
-----END PGP SIGNATURE-----

[Pete Becker]

Re: Random number generator.

On 2008-05-31 15:36:05 -0400, Sam <sam@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
>
jason.cipriani@ 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)

[James Kanze]

Re: Random number generator.

On May 31, 8:00 pm, Darío Griffo <dario.griffo.l is...@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((unsigne d)(next/65536) % 32768);
}

void mysrand(unsigne d 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:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[bilgekhan]

Re: Random number generator.

"Kai-Uwe Bux" <jkherciueh@gmx .netwrote:

Kai-Uwe Bux wrote:
>

jason.cipriani@ 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 =
636413622384679 3005ull; // cong 5 mod 8
>
static const unsigned long long c =
314159ull; // odd
>
public:
>
Line26 ( unsigned long seed = 0 )
: state ( 126871263818671 ull + a * seed )
{}
>
unsigned long min ( void ) const {
return ( 0 );
}
>
unsigned long max ( void ) const {
return ( 0xfffffffful );
}
>
unsigned long operator() ( void ) {
state = state * a + c & 0xfffffffffffff fffull;
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 & 0xfffffffffffff fffull;
} 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.