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)

Medick

Is this C or C++ (or objective-C?). The C++ standard library is much more suited to what you are trying to do, if I understand correctly what you are trying to do. – Tightwad

Either C / C++ or Objective-C is fine. Since my project is in objective-c, I can use C or C++ implementations as well. – Medick

Do you have C++11 support? – Saguenay

Yes. I have C++11 support. – Medick

Since you say weak PRNG is OK, something like rand( int seed, int n ) { return (seed * n) % 65537; } could work. – Epileptoid

Answer 1

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

Gens

You don't even need the discard. Each class can have its own instance, which is sufficient for the (amended) question – Damali

Answer 2

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.

Epileptoid

This is NOT a very good PRNG. Look more towards an algorithm like the Mersenne twister if you want more "random" results. – Briefless

I don't need to be "unpredictably" random. Just need enough randomness to look like noise to a human. This is for generating graphics. – Medick

I mainly code in Objective-C, so I just don't understand how your code works, or how I should use it. It looks like with each call to rand you will return the same number. – Medick

Rand::rand() change seed which is a member variable of class Rand. – Epileptoid

C++'s <random> would be very useful here, if your platform supports it. – Pigeontoed

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.

Geometrize

Unfortunately rand_r is limited to 32-bit state (assuming int is 32 bits). This gives you a max period of 2^32, which is very low, and makes it hard to get decent statistical properties without skewing the distribution away from uniform (which makes the period even worse). – Chilt

@R..the OP said he doesn't care much about the statistical properties. However, there's also nrand48() or jrand48() which also take an explicit seed argument. – Geometrize

Can you explain how this works ? This sounds like what I want, but I can't figure out how to use it. I have only one thread. – Medick

Yes, my comment was meant more for others reading the question in the future. – Chilt

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.

Melancholy

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

Berlioz

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.

Cordelier

Many PRNGs are Linear Congruential Generators where m is a power of two. In those cases, it is possible to calculate what the state will be in N generations without looping through each one, just like the article referenced in the question. If x(n+1) = (a*x(n)+c) mod m, then x(n+k) = (pow(a,k)*x(n)+(pow(a,k)-1)*c/(a-1)) mod m – Monoxide

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.

Semiyearly

All PRNGs have a finite number of states. Also, LFSRs are a class of PRNGs. – Keratin

I'm not sure how that's right. Some pseudorandom series are defined by an explicit algorithm to precompute each element. You might know them as block ciphers. – Melancholy