Two-way random number generator

Question

I need PRNG that will be not only repeatable, but also will be able to traverse it's internal states in two directions.

E.g

r = prng_from_seed(seed)
r.next # => 0.12332132412
r.next # => 0.57842057177
r.next # => 0.74782915912
r.prev # => 0.57842057177
r.next # => 0.74782915912

What relatively strong PRNG algorithms have this feature?

For which purpose? Your list are PRNG of classes K1 and K2. Do you also need classes K3 and K4 ? ==> https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Zertifizierung/Interpretationen/AIS_20_Functionality_Classes_Evaluation_Methodology_DRNG_e.pdf?__blob=publicationFile — SQL Police, Nov 21 '15 at 14:51
Floating point numbers suffer from exactness problems. Are you sure you don't want to use a lossless - integral - type instead? — Jongware, Nov 21 '15 at 14:54

score 3 · Answer 1 · answered Nov 21 '15 at 14:59

3

Use a simple counter as seed, that you increase with next and decrese with prev. Then use this counter as the seed for another random generator that you use to generate the random number.

answered Nov 21 '15 at 14:59

Ebbe M. Pedersen

7,250
3
27
47

1

It might be worth noting that instead of using another PRNG, you can use some block cipher (with a fixed, possibly secret key, which can be derived from initial seed) to encrypt the counter value and then transform the resulting (random) block into the output number somehow. – vlp Nov 21 '15 at 15:05

score 3 · Answer 2 · answered Nov 22 '15 at 15:05

There are RNG which have fast logarithmic (log2(N)) forward and backward skip-ahead (a.k.a. leap-frog). They are based upon the paper by F. Brown, "Random Number Generation with Arbitrary Stride," Trans. Am. Nucl. Soc. (Nov. 1994).

Relatively simple one is used in famous MC code MCNP, Fortran and C++ implementation https://github.com/Iwan-Zotow/LCG-PLE63, though it won't pass tests like Diehard.

A bit more complex, but of excellent quality are family of PCG random, at http://www.pcg-random.org/

This is too slow. Isn't this http://stackoverflow.com/a/16630535/1406702 much much faster? — happy_marmoset, Feb 11 '16 at 06:28

Matt Timmermans · Answer 3 · 2015-11-21T19:14:27.810

Pretty much ALL PRNGs have this feature, but nobody ever implements the go-to-previous state method.

Consider:

Since a PRNG has a finite-sized state, calling next() repeatedly will eventually get into a state you been in before.
If you start off in a state that will eventually be reached again by making N calls to next(), then you can always find a predecessor state by making N-1 calls to next().

Of course, in real life you would want a much more efficient way to implement prev(). How to do it would depend on the RNG, but it's generally not too hard.

Note that, in order to make the best use of their state, PRNGs are designed to have cycles that are as big as possible. Usually all accessible states are in the same cycle.

EDIT:

I should add that when people want to do this in real life, they often just use a counter as the internal state, and hash it (or encrypt it with a fixed key) to generate each random number. In a cryptographic context this is called "CTR MODE" encryption, which is googlable.

Of course if you do this, then you get random access to every state.

`but nobody ever implements the go-to-previous state method` Huh ?! Please check my answer — Severin Pappadeux, Nov 22 '15 at 15:06

Two-way random number generator

3 Answers3