How to get nth number in sequence of rand() directly without having to call rand() n times?

Question

According to my understanding, setting srand with a particular seed causes the sequence of calls to rand() to produce the same series of numbers each time for that particular seed:

Eg:

             srand(seed1);
             rand() // firstnumber (e.g.: 42)
             rand() // second number (e.g: 17)
             srand(seed1)
             rand() // first number (same as above (42))
             rand() // second number (same as above (17))

Is there a way to get the nth number in the sequence directly without having to call rand() n times ?

• For example, if I want the 17th random number in the series, I want to get the number in one call, instead of calling rand() 17 times.

• I cannot precompute and store the values

EDIT: I was looking at this article :

https://mathoverflow.net/questions/104915/pseudo-random-algorithm-allowing-o1-computation-of-nth-element

The answer on linear feedback shift registers seems to do it, but rather than implement it myself, I would rather use a trusted implementation, since this seems like a common problem.

EDIT: The reason I want to "jump" to the nth term, is because I use rand in different classes with different seeds, and I keep jumping back and forth between each class. I want the sequence in each class to continue where it left off, instead of starting from the first number each time. This is a single threaded application.

EDIT: When writing the post, I used the term PRNG. But really I'm just looking for a function which appears to produce random number. I'm using this for graphics, so there is no security problem. I use the random numbers to produce slight offsets in pixels.

• I just need a function which is fast.
• Appears to produce random numbers, but doesn't have to be of the kind used in security applications.
• Have to be able to calculate the nth number in O(1) time.

Edit: Made a mistake - storing state isn't enough. I need to calculate nth random number in series in O(1) time. Since within the same class there may be multiple calls for the same nth term, storing state won't be enough, and I need to compute the nth term in O(1)

Answer 1

Make your own rand and store one in each class. Of course this is the weakest PRNG. The point is you can have multiple PRNG active at once.

class Rand {
    int seed;
    const int a = 1103515245;
    const int c = 12345;
public:
    Rand();
    void srand( int );
    int rand();
};

Rand::Rand() : seed(123456789) {}

void Rand::srand( int s ) { seed = s; }

int Rand::rand()
{
  seed = a * seed + c;
  return seed;
}

The OP asks for "I use rand in different classes with different seeds". Each instance of Rand has its own seed. So place an instance of Rand in each object that needs its own seed.

Answer 2

All of the C++11 PRNGs have a "discard" function, e.g.

#include <random>
#include <iostream>

int main() {
    std::mt19937 rng;
    static const size_t distance = 5;

    rng.seed(0);
    rng.discard(distance);
    std::cout << "after discard 5: " << rng() << '\n';

    rng.seed(0);
    for (size_t i = 0; i <= distance; ++i) {
        std::cout << i << ": " << rng() << '\n';
    }
}

http://ideone.com/0zeRNq

after discard 5: 3684848379
0: 2357136044
1: 2546248239
2: 3071714933
3: 3626093760
4: 2588848963
5: 3684848379

Answer 3

Use rand_r(). With that function, the seed is not global and implicit. You pass the seed to use explicitly and the function updates it as it computes the next random number. That way, each class's stream of random numbers is independent of the others'.

---

Each object or each class (depending on your design needs) would store a seed value in an unsigned int variable. It would initialize it; for objects, in the init method; for classes, in +initialize. You could use the time or perhaps /dev/random for the initial value. If you initialize several such objects or classes in close succession, then using the time is a bad idea, since they may all happen at the "same" time (within the resolution of the clock you use).

After that, each time you want a random number, you call rand_r(&yourSeedVariable). That will return a pseudo-random value computed only from the passed-in seed, not using any implicit or global state. It uses the same algorithm as rand(). It also updates the seed variable such that the next call will produce the next random number in that sequence.

Any other object or class using this same technique would have an independent random sequence. Their calls to rand_r() would not affect this object's or class's and this object's or class's calls will not affect them. Same for any callers of rand().

---

To clarify a bit further. You said in one of the edits to your question:

The reason I want to "jump" to the nth term, is because I use rand in different classes with different seeds, and I keep jumping back and forth between each class. I want the sequence in each class to continue where it left off, instead of starting from the first number each time.

I am addressing that need with my suggestion. My suggestion does not address your question as phrased originally. It does not let you get the *n*th number in a pseudo-random sequence. It instead lets you use separate sequences in separate parts of your code such that they don't interfere with each other.

Answer 4

You want random access to a set of pseudorandom streams. You can get it by switching from std::rand() to a block cipher in counter mode (CTR) as your pseudorandom number generator. To read successive pseudorandom numbers, encrypt successive cleartext numbers. To read in some other order, encrypt numbers from the same range in some order order. Each class would then have its own seed, consisting of a key and initial value.

For example, one class's seed might be 8675309 and initial value 8008135. To read off successive random numbers, encrypt each of 8008136, 8008137, 8008138, 8008139, 8008140, ... with that key. To read off the 17th number in this sequence, encrypt (8008135 + 17) = 8008152.

Answer 5

You can use a 1:1 hash function on a 32-bit or 64-bit counter. For your hash you can adapt any method that a PRNG would use as its feedback and/or tempering function, like this one from Wikipedia's xorshift page:

uint64_t state;

void srand(uint64_t seed) {
  state = seed;
}

uint64_t hash(uint64_t x) {
  x ^= x >> 12;
  x ^= x << 25;
  x ^= x >> 27;
  return x * 2685821657736338717ull;
}

uint32_t rand(void) {
  return hash(state++) >> 32;
}

uint32_t rand(uint32_t n) {
  return hash(n) >> 32;
}

Answer 6

The main thing about PRNGs is that (in common, fast implementations) next value depends on previous. So no, you can't get Nth value without calculating all the previous N-1 ones.

Answer 7

Short answer: no.

Longer answer: Pseudorandom series are "random" in that the computer cannot pre-compute the series without knowing the previously pre-computed item (or the seed), but are "pseudo" in that the series is reproducible using the same seed.

From using Google-fu, LSFR's require a finite number of states. PRNG's, which is what you're trying to get, do not.