vendredi 11 août 2017

Fisher Yates algorithm gives back same order of numbers in parallel started programs when seeded over the system time

I start several C / C++ programs in parallel, which rely on random numbers. Fairly new to this topic, I heard that the seed should be done over the time.

Furthermore, I use the Fisher Yates Algorithm to get a list with unique random shuffled values. However, starting the program twice in parallel gives back the same results for both lists.

How can I fix this? Can I use a different, but still relient seed?

My simple test code for this looks like this:

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#include <time.h>
static int rand_int(int n) {

        int limit = RAND_MAX - RAND_MAX % n;
        int rnd;

        do {
                rnd = rand();
        }
        while (rnd >= limit);
        return rnd % n;
}


void shuffle(int *array, int n) {

        int i, j, tmp;
        for (i = n - 1; i > 0; i--) {
                j = rand_int(i + 1);
                tmp = array[j];
                array[j] = array[i];
                array[i] = tmp;
        }
}


int main(int argc,char* argv[]){

        srand(time(NULL));
        int x = 100;
        int randvals[100];
        for(int i =0; i < x;i++)
                randvals[i] = i;

        shuffle(randvals,x);
        for(int i=0;i < x;i++)
                printf("%d %d \n",i,randvals[i]);

}

I used the implementation for the fisher yates algorithm from here:

http://ift.tt/2uxxZUH

I started the programs in parallel like this:

./randomprogram >> a.txt & ./randomprogram >> b.txt

and then compared both text files, which had the same content.




Aucun commentaire:

Enregistrer un commentaire