«

On May 31, 7:09*pm, "jason.cipri...@gmail.com"
<jason.cipri...@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?).
>
> 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

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.com> wrote:
> > 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) % 3276;
> }

> 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. 198. 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:
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

"Kai-Uwe Bux" <> wrote:
> Kai-Uwe Bux wrote:
>
> > 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)
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.

bilgekhan wrote:

> "Kai-Uwe Bux" <> wrote:
>> Kai-Uwe Bux wrote:
>>
>> > 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

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