Existe algum gerador de números pseudo-aleatórios (não criptográficos) que pode pular / soltar N desenha em O (1), ou talvez O (log N), mas menor que O (N

Especialmente para aplicações paralelas, seria vantajoso ter um gerador do tipo acima. Imagem que você deseja gerar uma matriz de números aleatórios. Pode-se escrever um programa paralelo para esta tarefa e propagar o gerador de números aleatórios para cada thread independentemente. No entanto, os números na matriz não seriam os mesmos que no caso seqüencial (exceto na primeira metade, talvez

Se existir um gerador de números aleatórios do tipo acima, o primeiro thread poderá propagar com a semente usada para a implementação seqüencial. O segundo thread também pode propagar com essa semente e, em seguida, soltar / pular amostras N / 2 que são geradas pelo primeiro thread. A matriz de saída seria então idêntica à caixa serial (teste fácil), mas ainda gerada em menos tempo. Abaixo está algum pseudo-código.

#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;
}

Muito obrigado a todos pela ajuda. Eu sei que pode haver uma prova de que esse gerador não pode existir e ser "pseudo-aleatório" ao mesmo tempo. Sou muito grato por qualquer dica sobre onde encontrar mais informações.