What is the most correct way to generate random nu

问题:

I have several threads running concurrently and each of them must generate random numbers. I want to understand if there is a pattern to follow, to understand if it is correct to initialize the random generator with srand in the main thread or if every thread must initialize its own random generator. It seems that rand/srand have not been designed to be used with threads and I'm wondering how I can deal with threads and random numbers together. Thanks

EDIT: I need pure random numbers, but I'm also interested in generating a deterministic sequence for testing purposes. I'm on linux, but I prefer to write code as portable as possible.

回答1:

On Linux you can use the rand_r() for a mediocre generator or the drand48_r() function for a much better one. Both are thread safe replacements for rand() and drand48(), by taking a single argument consisting of the current state, instead of using global state.

With regard to your question on initialization, both of the generators above allow you to seed at whatever point you desire, so you are not forced to seed them before spawning your threads.

回答2:

When working with threads and doing e.g simulations or so it is very important that you have the random generators independent. First, dependencies between them can really bias your results and then mechanisms for access control to the state of the random generator will most likely slow down execution.

On POSIX systems (where you seem to be) there is the *rand48 family of functions where erand48, nrand48 and jrand48 take the state of the random generator as input values. So you can easily have independent states in each thread. Those you can initialize with a known number (e.g the number of your thread) and you'd have a reproducible sequence of random numbers. Or you initialize it with something non-predicable such as the current time & the number to have sequences that vary for each execution.

回答3:

On Windows you can use the rand_s() function, which is thread safe. If you are already using Boost, then boost::random is competent (although I appreciate this is tagged C, not C++).

回答4:

rand_r is thread-safe but also is reentrant.

Code below generates uint128_t pseuso-random numbers using xorshift algorithm.

Additional properties:

• shared-reentrant
• lock-free
• thread-safe
• ultrafast
• seeded from two variant sources of enthropy

uintx_types.h:

#ifndef UINTX_TYPES_H_INCLUDED
#define UINTX_TYPES_H_INCLUDED

#include <inttypes.h>
#include <ctype.h>

typedef __uint128_t     uint128_t;
typedef __uint64_t      uint64_t;

#define UINT128_C(hi, lo)   (((uint128_t)(hi) << 64) | (uint128_t)(lo))
#define UINT128_MIN         UINT128_C( 0x0000000000000000, 0x0000000000000000 )
#define UINT128_0           UINT128_MIN
#define UINT128_MAX         (~(UINT128_0) - 1) 

#endif // UINTX_TYPES_H_INCLUDED

lf.h:

#ifndef LF_H_INCLUDED
#define LF_H_INCLUDED

#define AAF(ADDR, VAL)          __sync_add_and_fetch((ADDR), (VAL))

#endif // LF_H_INCLUDED

rand.h:

#ifndef RAND_H_INCLUDED
#define RAND_H_INCLUDED

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#include <limits.h>
#include <fcntl.h>
#include <sys/types.h>
#include <unistd.h>

#include "lf.h"
#include "uintx_types.h"


#define URANDOM     "/dev/random"   

void        srand_init(void);
uint128_t   rand_range_128(uint128_t min, uint128_t max);

#endif // RAND_H_INCLUDED

rand.c:

#include "rand.h"

uint64_t    r[2];

uint64_t xorshift64star(int index) 
{   
    uint64_t    x;

    x = r[index];
    x ^= x >> 12; // a
    x ^= x << 25; // b
    x ^= x >> 27; // c
    x = x * UINT64_C(2685821657736338717);
    return AAF(&r[index], x);
}

void srand_init(void)
{
    struct timespec ts;
    size_t          nbytes;
    ssize_t         bytes_read;
    int             fd;

    clock_gettime(CLOCK_REALTIME, &ts);
    r[0] = (uint64_t)(ts.tv_sec * 1.0e9 + ts.tv_nsec);
    xorshift64star(0);

    if ((fd = open(URANDOM, O_RDONLY, S_IRUSR | S_IRGRP | S_IROTH)) == -1)
    {
        r[1] = r[0] + 1;
        xorshift64star(1);
    }
    else
    {
        nbytes = sizeof(r[1]);
        bytes_read = read(fd, &r[1], nbytes);
        if ((bytes_read == 0) || (r[1] == 0ull))
        {
            r[1] = r[0] + 1;
            xorshift64star(1);
        }
        close(fd);
    }
}

uint64_t rand_64(void)
{
    return xorshift64star(0);
}

uint128_t rand_128(void) 
{
    uint128_t       r;

    r = xorshift64star(0);
    r = (r << 64) | xorshift64star(1);
    return r;
}


uint128_t rand_range_128(uint128_t min, uint128_t max)
{
    return (rand_128() % (max+1-min))+min;
}

test.c:

#define KEYS 1000

int main(int argc, char **argv)
{
    int             i;
    uint128_t       key;

    srand_init();

    for(i = 0; i <= KEYS; i++)
    {
        key = rand_range_128(UINT128_MIN, UINT128_MAX);
        printf("%016"PRIx64"%016"PRIx64"\n", (uint64_t)(key >> 64), (uint64_t)key);

    }
    return 0;
}

Compile with gcc(4.9.2) under Linux.

回答5:

This link provides some code for reading from /dev/random -- which should be thread-safe -- and the question is along the same lines:

Is reading /dev/urandom thread-safe?

回答6:

On Linux systems you can use a function like:

size_t random_between_range( size_t min, size_t max ){
    unsigned short state[3];
    unsigned int seed = time(NULL) + (unsigned int) pthread_self();
    memcpy(state, &seed, sizeof(seed));
    return min +  nrand48(state) % (max - min );
}

Here I have to say that I don´t really know if numbers generated by this function fit to normal distribution in other words if this function is a valid RNG in the range (min,max) but at least worked for me to write a simple benchmark that required some random numbers.

As you can see, the function utilizes the POSIX thread id in order to re-arrange the random seed. Doing so, each thread has it own random seed instead of using global state depending on time(NULL)