bidirectional pseudo random number generator

[dolomighty]

many forms of PRN generator are recursive functions like x1 = f( x0 )
wich means the new RND comes from the computation of some algo on a previous value of the same algo.

for instance, the C rand() function works like this... simply the fact of passing the previous value on and on is hidden to the user.

so, this fact estabilishes a relation, where the stream of numbers comes in a given order: number x1 will always follow number x0.

now, my question is this: is there a theoretical way to create an algorithm wich generates the numbers in REVERSE order, given the forward algorithm ?
are there studies made on this subject ?


...i personally doubt of it, because many PRNG are based on loss of information, but who knows...

thanks in advance.

[TheCPUWizard]

Well....

the rand() and related functions to not keep the previous value per se. They keep an internal value that is typically of a longer bit length than the exposed value.

This is the information loss that you refer to and does typically make the algoritm non-reversible from an external standpoint.

If the internal value had the same bit length (or the exposed value was actually used to comput the next value), the sequence would repeat immediatly upon the first duplication of a number.

If many cases it IS possible to generate an inverst ordered sequence algorithm. But this would require knowing the internal value. If modification of the existing algorithm is permidded, this value could be exposed. If not, then you would need to run the two algorithms in lock step to keep track of the internal value externally.

The real question if why???? :confused:

[dolomighty]

>If the internal value had the same bit length (or the exposed value was actually
>used to comput the next value), the sequence would repeat immediatly upon
>the first duplication of a number.

yes, indeed, i didn't thought about that: in the end, good prng cannot be recursive for this reason... and all the random generators i' ve designed and implemented all use higher bit number stores to address the problem. :)



however, reversible prng could be used in many applications, mainly in the contest of... let's call it automatic data generation: since a prng is a somewhat fast and memory cheap way to obtain repeatable randomness, this can have application in many areas of computing: CG to tell just one.

an example could be an animation where there's a car wich runs on a road with trees on the sides: you could store all your infos into a db and render it, or you could let algorithms create the informations on the fly.

with a naive approach, if the car goes forward for a while and then comes back, the trees sequence would be different, since a simple prng always generates a stream of numbers, without regard of direction.

a bunch of reversible prn generators could be the heart of the system; instead of having explicit infos, you do it implicitly: this can help artists to focus only where they want at that time, letting the machine "create" where and in the way they want... someway like that flavor of genetic/evolutionary algos where the natural selection process is carried out by the user.



by the way, on a strictly technical point of view, i've realized that since some information is lost when a prng works, to create a reverse function is impossible without some historic information, besides the standard internal store.

i think the way to go is with hashing functions: if i hash a 32bit integer, i will end up with a virtual array of 4 billion random numbers, probably more than enough i'll ever need :)

[TheCPUWizard]

For items such as a varing background, there may be entirely different arrangements (algorithms) that are better suited.

Are even distribution and/or trends really an issue?

How many different (long and short term) sequences are really needed?