Is there a random number generator which can skip/

问题:

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.

回答1:

Sure. Linear Conguential Generator and its descendants could skip generation of N numbers in O(log(N)) time. It is based on paper of F.Brown, link.

Here is an implementation of the idea, C++11.

回答2:

As kindly indicated by Severin Pappadeux, the C, C++ and Haskell implementations of a PCG variant developed by M.E. O'Neill provides an interface to such jump-ahead/jump-back functionality: herein.

Function names are: advance and backstep, which were briefly documented hereat and hereat, respectively

Quoting from the webpage (accessed at the time of writing):

... a random number generator is like a book that lists page after page of statistically random numbers. The seed gives us a starting point, but sometimes it is useful to be able to move forward or backwards in the sequence, and to be able to do so efficiently.

The C++ implementation of the PCG generation scheme provides advance to efficiently jump forwards and backstep to efficiently jump backwards.