mercredi 30 janvier 2019

Is there a random number generator which can skip/drop N draws in O(1)?

Is there any (non-cryptographic) pseudo random number generator that can skip/drop N draws in O(1), or maybe O(log N) but smaller than O(N).


Especially for parallel applications it would be of advantage to have a generator of the above type. Image you want to generate an array of random numbers. One could write a parallel program for this task and seed the random number generator for each thread independently. However, the numbers in the array would then not be the same as for the sequential case (except for the first half maybe).

If a random number generator of the above type would exist, the first thread could seed with the seed used for the sequential implementation. The second thread could also seed with this seed and then drop/skip N/2 samples which are generated by the first thread. The output array would then be identical to the serial case (easy testing) but still generated in less time. Below is some pseudo code.

#define _POSIX_C_SOURCE 1
#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

void rand_r_skip(unsigned int *p_seed, int N)
{
    /* Stupid O(N) Implementation */
    for (int i = 0; i < N; i++)
    {
        rand_r(p_seed);
    }
}

int main()
{
    int N = 1000000;
    unsigned int seed = 1234;
    int *arr = (int *)malloc(sizeof(int) * N);

#pragma omp parallel firstprivate(N, seed, arr) num_threads(2)
    {
        if (omp_get_thread_num() == 1)
        {
            // skip the samples, obviously doesn't exist
            rand_r_skip(&seed, N / 2);
        }
#pragma omp for schedule(static)
        for (int i = 0; i < N; i++)
        {
            arr[i] = rand_r(&seed);
        }
    }
    return 0;
}

Thank you all very much for your help. I do know that there might be a proof that such a generator cannot exist and be "pseudo-random" at the same time. I am very grateful for any hints on where to find further information.




Aucun commentaire:

Enregistrer un commentaire