¿Hay algún generador de números pseudoaleatorio (no criptográfico) que pueda omitir / soltar N sorteos en O (1), o tal vez O (log N) pero más pequeño que O (N).

Especialmente para aplicaciones paralelas, sería una ventaja tener un generador del tipo anterior. Imagen que desea generar una matriz de números aleatorios. Se podría escribir un programa paralelo para esta tarea y sembrar el generador de números aleatorios para cada hilo de forma independiente. Sin embargo, los números en la matriz no serían los mismos que para el caso secuencial (a excepción de la primera mitad quizás).

Si existiera un generador de números aleatorios del tipo anterior, el primer subproceso podría iniciarse con el inicializado utilizado para la implementación secuencial. El segundo hilo también podría sembrar con este semilla y luego soltar / omitir N / 2 muestras generadas por el primer hilo. La matriz de salida sería idéntica a la caja en serie (prueba fácil) pero aún se generaría en menos tiempo. A continuación hay un pseudocó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;
}

Muchas gracias a todos por su ayuda. Sé que puede haber una prueba de que dicho generador no puede existir y ser "pseudoaleatorio" al mismo tiempo. Estoy muy agradecido por cualquier pista sobre dónde encontrar más información.