Random.Next () - search Nth.Next ()

Question

For sequentially specified Random:

Random r = new Random(0);

Calling r.Next() sequentially produces the same series; so is there a way to quickly detect an n-dimensional value in this series without calling r.Next() N times?

My script is a huge array of values ​​created using r.Next() . An application sometimes reads a value from an array at arbitrary indices. I would like to optimize memory usage by excluding an array and instead creating values ​​on demand. But coarse forcing r.Next() 5 million times to mimic the 5 millionth index of an array is more expensive than storing an array. Is it possible to shorten the path to the value of N.Next (), without / with a smaller loop?

Answer 1

In theory, if you knew the exact algorithm and initial state, you could duplicate the series, but the end result would be just identical to calling r.next ().

Depending on how “good” you need your random numbers, you might consider creating your own PRNG based on a linear congruent generator that is relatively easy / quick to generate numbers for. If you can live with a “bad” PRNG, there are probably other algorithms that could be better used for your purpose. Whether this will be faster / better than just storing a large array of numbers from r.next () is another question.

Answer 2

I do not know the PRNG details used in BCL, but I assume that it will be extremely difficult / impossible for you to find a good closed solution for the Nth value of the series.

How about this workaround:

Make the seed for the random number generator the desired index, and then select the first generated number. It is equally “deterministic” and gives you a wide range of possibilities for reproduction in O (1) space.

 static int GetRandomNumber(int index) { return new Random(index).Next(); } 

Answer 3

No, I do not believe that there is. For some RNG algorithms (such as linear congruent generators) it is in principle possible to get an n-dimensional value without repeating using n steps, but the Random class does not provide a way to do this.

I’m not sure if the algorithm used is fundamental - this is an option (details not disclosed in the documentation) from Knuth’s tear-down RNG, and it looks like the original Knuth RNG should be equivalent to some polynomial arithmetic thing that would allow access to n- value, but (1) I didn’t actually check it, and (2) any changes made by Microsoft may violate this.

If you have a good enough scrambling function f, you can use f (0), f (1), f (2), ... as your sequence of random numbers instead of f (0), f (f (0) ), f (f (f (0))), etc. (the latter roughly correspond to most RNGs), and then, of course, it is trivial to start the sequence at any point that you like. But you need to choose a good f, and it will probably be slower than the standard RNG.

Answer 4

You can create your own vocabulary on demand "indexes" and "random values". This assumes that you will always “require” the indexes in the same order each time the program starts, or that you don’t care if the results are the same every time the program starts.

 Random rnd = new Random(0); Dictionary<int,int> randomNumbers = new Dictionary<int,int>(); int getRandomNumber(int index) { if (!randomNumbers.ContainsKey(index)) randomNumbers[index] = rnd.Next(); return randomNumbers[index]; }