Generating random numbers with next and previous support?
How do I write two functions to generate random numbers that support next and previous?
I mean how to write two functions: next_number()
and previous_number()
that the function next_number()
generates a new random number and the function previous_number()
generates the previously generated random number.
eg:
int next_number()
{
// ...?
}
int previous_number()
{
// ...?
}
int num;
// Forward random number generating.
// ---> 54, 86, 32, 46, 17
num = next_number(); // num = 54
num = next_number(); // num = 86
num = next_number(); // num = 32
num = next_number(); // num = 46
num = next_number(); // num = 17
// Backward random number generating.
// <--- 17, 46, 32, 86, 54
num = previous_number(); // num = 46
num = previous_number(); // num = 32
num = previous_number(); // num = 86
num = previous_number(); // num = 54
source to share
You can trivially do this with a pseudo random function (PRF).
These functions take a key and a value and output a pseudo-random number based on them. You pick a key from / dev / random that stays the same to run the program, and then feed the function an integer that you increment to go forward or decrement to go backward.
Here's an example in pseudocode:
initialize():
Key = sufficiently many bytes from /dev/random
N = 0
next_number():
N = N + 1
return my_prf(Key, N)
previous_number():
N = N - 1
return my_prf(Key, N)
Strong, pseudo-random functions are found in most cryptographic libraries. As Richie points out, you can also use any encryption function (encryption functions are pseudo-random permutations, a subset of PRFs, and the period is so large that the difference doesn't matter).
source to share
Some linear congruential generators (common but not very good PRNGs) are reversible.
They work next = (a * previous + c) mod m
. It is reversible if it a
has a modular multiplicative inverse mod m
. This is often the case because it is m
often a power of two and a
usually odd.
For example, for "MSVC" parameters from the table from the first link:
- m = 2 32
- a = 214013
- c = 2531011
Reverse:
previous = (current - 2531011) * 0xb9b33155;
With the types selected to make it work modulo 2 32 .
source to share
A fairly straightforward way to generate an indexable pseudo-random sequence - that is, a sequence that looks random but can be traversed in any direction - is to pick some (good enough) encryption algorithm and a fixed encryption key, and then define:
sequence(i): encrypt(i, known_key)
You don't need to know the meaning i
, because you can decipher it from the number:
next(r): encrypt(decrypt(r, known_key) + 1)
prev(r): encrypt(decrypt(r, known_key) - 1)
Therefore, i
it should not be a small integer; since the only arithmetic you need to do is addition and subtraction with a small integer, the implementation of bignam is trivial. So if you want 128-bit pseudo data, you can set the first one i
as a 128-bit random number extracted from /dev/random
.
You must store the entire value i
in static storage and the pseudo random number period cannot exceed the range i
. This will be true for any solution to this problem: as operators next()
and prev()
must be functions, each value has a unique successor and predecessor and therefore can only appear once in the value cycle. This is not at all the same as, for example, the Mersenne twister, whose cycle is much larger than 2 32 .
source to share
Suppose you have a linear congruent sequence S
defined by
S[0] = seed
S[i] = (p * S[i-1] + k) % m
for some p
, m
, k
such that gcd(p, m) == 1
. Then you can find q
to (p * q) % m == 1
and calculate:
S[i-1] = (q * (S[i] - k)) % m
In other words: if you choose the appropriate p
and precompute q
, you can go through your sequence in any order in O(1)
time.
source to share
I think you are asking for a random number generator that is deterministic. It doesn't make sense, because if it is deterministic, it is not random. The only solution is to create a list of random numbers and then step back and forth in that list.
PS! I know that all PRNG-s software is deterministic. You can of course use this to create the functionality you want, but don't be fooled, it has nothing to do with randomness. If your software design requires a deterministic PRNG, you can skip the PRNG part altogether.
source to share