Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the most correct way to generate random numbers in C with pthread

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.

like image 420
Raffo Avatar asked Oct 17 '11 18:10

Raffo


4 Answers

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.

like image 191
Michael Goldshteyn Avatar answered Sep 18 '22 20:09

Michael Goldshteyn


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.

like image 38
Jens Gustedt Avatar answered Sep 20 '22 20:09

Jens Gustedt


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++).

like image 37
Alastair Maw Avatar answered Sep 18 '22 20:09

Alastair Maw


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.

like image 23
Dawid Szymański Avatar answered Sep 20 '22 20:09

Dawid Szymański