64 bits Seeds for random generators

Question

I am currently running a multithreading simulation application with 8+ pipes (threads). These pipes run a very complex code that depends on a random sequence generated by a seed. The sequence is then boiled down to a single 0/1.

I want this "random processing" to be 100% deterministic after passing a seed to the processing pipe from the main thread. So, I can replicate the results in a second run.

So, for example: (I have this coded and it works)

Pipe 1 -> Seed: 123 -> Result: 0
Pipe 2 -> Seed: 123 -> Result: 0
Pipe 3 -> Seed: 589 -> Result: 1

The problem arises when I need to run 100M or more of these processes and then average the results. It may be the case only 1 of the 100M is a 1, and the rest are 0. As it is obvious, I cannot sample 100M random values with 32bit seeds feeding to srand().

Is it possible to seed with a 64bit seed in VS2010 to srand(), or use a equivalent approach?

Does rand() repeat itself after 2^32 or does not (has some inner hidden state)?

Thanks

Answer 1

You can use C++11's random facilities to generate random numbers of a given size and seed size, though the process is a bit too complicated to summarize here.

For example, you can construct an std::mersenne_twister<uint64_t, ...> and seed it with a 64-bit integer, then acquire random numbers within a specified distribution, which seems to be what you're looking for.

Answer 2

A simple 64-bit LCG should meet your needs. Bit n (counting from the least significant as bit 1) of an LCG has period at most (and, if parameters are chosen correctly, then exactly) 2^n, so avoid using the lower bits if you don't need them, and/or use a tempering function on the output. A sample implementation can be found in my answer to another question here:

https://stackoverflow.com/a/19083740/379897

And reposted:

static uint32_t temper(uint32_t x)
{
    x ^= x>>11;
    x ^= x<<7 & 0x9D2C5680;
    x ^= x<<15 & 0xEFC60000;
    x ^= x>>18;
    return x;
}
uint32_t lcg64_temper(uint64_t *seed)
{
    *seed = 6364136223846793005ULL * *seed + 1;
    return temper(*seed >> 32);
}

Answer 3

you could use an XOR SHIFT psuedorandom number generator

It is fast and works a treat - this is the actual generation part from my implementation class of it. I found the information on this algorithm in a wikipedia search on psuedorandom number generators...

uint64_t XRS_64::generate(void)
{
    seed ^= seed >> 12; // a
    seed ^= seed << 25; // b
    seed ^= seed >> 27; // c
    return seed  * UINT64_C(2685821657736338717);
}

it is fast and for initialisation you do that inside the constructor

XRS_64::XRS_64()
{
    seed = 6394358446697381921;
}

seed is an unsigned int 64 bit variable and it is declared inside the class.

class XRS_64
{
public:
    XRS_64();
    ~XRS_64();
    void init(uint64_t newseed);
    uint64_t generate();

private :
    uint64_t seed; /* The state must be seeded with a nonzero value. */
};

Answer 4

I can't answer your questions, but if you find out you can't do what you want, you can implement your own pseudo-random algorithm generator which takes a uint64_t as a seed. There are better algorithms for this purpose if you want some more serious generator (for cryptography purposes, for instance), but LCG is the easiest I've seen to be implemented.

EDIT

Actually you cannot use a 64-bit seed for the rand() function. You will have to go for your own. In this Wikipedia table there some parameters used by MMIX Donald Knuth to implement it. Be aware that depending on the parameters you use, your random number generator period will have a much lesser value than 2^64 and because of the multiplications, you may need a Big Number library to handle the math operations.

Answer 5

My recommendation is that you take direct control over the process and set up your own high-quality random number generator. None of the answers here have been properly tested or validated - and that is an important criterion that needs to be taken into account.

High-quality random number generators can be made for large periods even on 16-bit and 32-bit machines by just running several of them in parallel - subject to certain preconditions. This is described, in further depth, here

P.L'Ecuyer, ‟Efficient and portable combined random number generators”, CACM 31(6), June 1988, 742-751.

with testing & validation results also provided. Accessible versions of the article can be found on the net.

For a 32-bit implementation the recommendation issued there was to take M₀ = 1 + 2×3×7×631×81031 (= 2³¹ - 85) and M₁ = 1 + 2×19×31×1019×1789 (= 2³¹ - 249) to produce a random number generator of period (M₀ - 1)(M₁ - 1)/2 ≡ 2×3×7×19×31×631×1019×1789×81031 ≡ 2⁶¹ - 360777242114. They also posted a recommendation for 16-bit CPU's.

The seeds are updated as (S₀, S₁) ← ((A₀×S₀) mod M₀, (A₁×S₁) mod M₁), and a 32-bit value may be produced from this as S₀ - S₁ with the result adjusted upward by M₀ - 1 if S₀ ≤ S₁. If (S₀, S₁) is initialized to integer values in the interval [0,M₀)×[0,M₁), then it remains in that interval with each update. You'll have to modify the output value to suit your needs, since their version is specifically geared toward producing strictly positive results; and no 0's.

The preconditions are that (M₀ - 1)/2 and (M₁ - 1)/2 be relatively prime and that A₀² < M₀, A₁² < M₁; and the values (A₀, A₁) = (40014, 40692) were recommended, based on their analysis. Also listed were optimized routines that allow all the computations to be done with 16-bit or 32-bit arithmetic.

For 32-bits the updates were done as (S₀, S₁) ← (A₀×(S₀ - K₀×Q₀) - K₀×R₀, A₁×(S₁ - K₁×Q₁) - K₁×R₁) with any S₀ < 0 or S₁ < 0 results adjusted upward, respectively, to S₀ + M₀ or S₁ + M₁; where (K₀, K₁) = (S₀ div Q₀, S₁ div Q₁), (Q₀, Q₁) = (M₀ div A₀, M₁ div A₁) and (R₀, R₁) = (M₀ mod A₀, M₁ mod A₁).