P: n/a

Hi all,
I was wondering if there is a random generator that is "reversible". I
need to go back in time in my application and still need to use
deterministic random numbers. Most of RNG implement the Next function
but what about a Prev ?
I know I can use an array to store X last values but I'm more
interested to know if it exist something that allows to go backwards.
Also I can't really afford to use the same seed and loop until i get
the previous value.
Thank you !  
Share this Question
P: n/a
 ki******@gmail.com said:
Hi all,
I was wondering if there is a random generator that is "reversible". I
need to go back in time in my application and still need to use
deterministic random numbers. Most of RNG implement the Next function
but what about a Prev ?
Most PRNGs are lossy (in terms of reversibility), relying on a modulo
operation to jump around the number space. But why can't you just push
each generated number onto a stack? Then you can just pop and reseed
whenever you need to go "back in time".

Richard Heathfield <http://www.cpax.org.uk>
Email: http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place"  dmr 29 July 1999  
P: n/a

On Oct 9, 1:49 am, kitti...@gmail.com wrote:
Hi all,
I was wondering if there is a random generator that is "reversible". I
need to go back in time in my application and still need to use
deterministic random numbers. Most of RNG implement the Next function
but what about a Prev ?
I know I can use an array to store X last values but I'm more
interested to know if it exist something that allows to go backwards.
Also I can't really afford to use the same seed and loop until i get
the previous value.
This is really OT for c.l.c, someplace like comp.programming would be
better, and sci.crypt would be excellent, except that sci.scrypt has
been totally DOS'd for the past few months.
Anyway, it's not hard to do, but you do need to decide on how good you
want the psuedo random numbers to be. Basically use a counter, and
then transform it into a random number, and appropriate increment or
decrement the counter as appropriate for your next_rand or prev_rand
function. If you use AES as your transform, you'll essentially be
using AES in the well understood CTR ("counter") mode, and you'll
produce pretty darn good "random" numbers. If you want something
rather simpler (and faster), but can live with "random" numbers of
considerably lesser quality, you could do something like bit reversing
the counter and then "mod 32767" it.  
P: n/a

On Oct 9, 4:20 pm, Richard Heathfield <r...@see.sig.invalidwrote:
kitti...@gmail.com said:
Hi all,
I was wondering if there is a random generator that is "reversible". I
need to go back in time in my application and still need to use
deterministic random numbers. Most of RNG implement the Next function
but what about a Prev ?
Most PRNGs are lossy (in terms of reversibility), relying on a modulo
operation to jump around the number space. But why can't you just push
each generated number onto a stack? Then you can just pop and reseed
whenever you need to go "back in time".

Richard Heathfield <http://www.cpax.org.uk>
Email: http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place"  dmr 29 July 1999
The problem is that if let's say I have to generate 1000 random in a
sec and need to store 100 min of random, it's not really going to be
good for memory.  
P: n/a

On Oct 9, 4:22 pm, "robertwess...@yahoo.com" <robertwess...@yahoo.com>
wrote:
On Oct 9, 1:49 am, kitti...@gmail.com wrote:
Hi all,
I was wondering if there is a random generator that is "reversible". I
need to go back in time in my application and still need to use
deterministic random numbers. Most of RNG implement the Next function
but what about a Prev ?
I know I can use an array to store X last values but I'm more
interested to know if it exist something that allows to go backwards.
Also I can't really afford to use the same seed and loop until i get
the previous value.
This is really OT for c.l.c, someplace like comp.programming would be
better, and sci.crypt would be excellent, except that sci.scrypt has
been totally DOS'd for the past few months.
Anyway, it's not hard to do, but you do need to decide on how good you
want the psuedo random numbers to be. Basically use a counter, and
then transform it into a random number, and appropriate increment or
decrement the counter as appropriate for your next_rand or prev_rand
function. If you use AES as your transform, you'll essentially be
using AES in the well understood CTR ("counter") mode, and you'll
produce pretty darn good "random" numbers. If you want something
rather simpler (and faster), but can live with "random" numbers of
considerably lesser quality, you could do something like bit reversing
the counter and then "mod 32767" it.
That answer my question, thank you very much ! And sorry for posting
in the wrong places.  
P: n/a

On Oct 9, 4:49 pm, kitti...@gmail.com wrote:
On Oct 9, 4:22 pm, "robertwess...@yahoo.com" <robertwess...@yahoo.com>
wrote:
On Oct 9, 1:49 am, kitti...@gmail.com wrote:
Hi all,
I was wondering if there is a random generator that is "reversible". I
need to go back in time in my application and still need to use
deterministic random numbers. Most of RNG implement the Next function
but what about a Prev ?
I know I can use an array to store X last values but I'm more
interested to know if it exist something that allows to go backwards.
Also I can't really afford to use the same seed and loop until i get
the previous value.
This is really OT for c.l.c, someplace like comp.programming would be
better, and sci.crypt would be excellent, except that sci.scrypt has
been totally DOS'd for the past few months.
Anyway, it's not hard to do, but you do need to decide on how good you
want the psuedo random numbers to be. Basically use a counter, and
then transform it into a random number, and appropriate increment or
decrement the counter as appropriate for your next_rand or prev_rand
function. If you use AES as your transform, you'll essentially be
using AES in the well understood CTR ("counter") mode, and you'll
produce pretty darn good "random" numbers. If you want something
rather simpler (and faster), but can live with "random" numbers of
considerably lesser quality, you could do something like bit reversing
the counter and then "mod 32767" it.
That answer my question, thank you very much ! And sorry for posting
in the wrong places. Hide quoted text 
 Show quoted text 
I missed something, when you say "you could do something like bit
reversing
the counter and then "mod 32767" it." How would I reverse this ?  
P: n/a

On Oct 9, 5:23 pm, kitti...@gmail.com wrote:
On Oct 9, 4:49 pm, kitti...@gmail.com wrote:
On Oct 9, 4:22 pm, "robertwess...@yahoo.com" <robertwess...@yahoo.com>
wrote:
On Oct 9, 1:49 am, kitti...@gmail.com wrote:
Hi all,
I was wondering if there is a random generator that is "reversible". I
need to go back in time in my application and still need to use
deterministic random numbers. Most of RNG implement the Next function
but what about a Prev ?
I know I can use an array to store X last values but I'm more
interested to know if it exist something that allows to go backwards.
Also I can't really afford to use the same seed and loop until i get
the previous value.
This is really OT for c.l.c, someplace like comp.programming would be
better, and sci.crypt would be excellent, except that sci.scrypt has
been totally DOS'd for the past few months.
Anyway, it's not hard to do, but you do need to decide on how good you
want the psuedo random numbers to be. Basically use a counter, and
then transform it into a random number, and appropriate increment or
decrement the counter as appropriate for your next_rand or prev_rand
function. If you use AES as your transform, you'll essentially be
using AES in the well understood CTR ("counter") mode, and you'll
produce pretty darn good "random" numbers. If you want something
rather simpler (and faster), but can live with "random" numbers of
considerably lesser quality, you could do something like bit reversing
the counter and then "mod 32767" it.
That answer my question, thank you very much ! And sorry for posting
in the wrong places. Hide quoted text 
 Show quoted text 
I missed something, when you say "you could do something like bit
reversing
the counter and then "mod 32767" it." How would I reverse this ? Hide quoted text 
 Show quoted text 
Ok stupid question nevermind.
/me jump off the window  
P: n/a
 ki******@gmail.com said:
<snip>
>
I missed something, when you say "you could do something like bit
reversing
the counter and then "mod 32767" it." How would I reverse this ?
You don't. What he's suggesting (and it's a very good idea) is that you
define your own PRNG that is sensitively dependent on an integer counter.
Then, rather than have each number rely on the previous one, you have it
rely *only* on the counter.
So for example, you might do something like this:
#include <stdio.h>
/* this function just reverses the bits in an unsigned long int.
It's a bit wordy, and you can probably crunch it down quite a lot.
*/
unsigned long int bitreverse(unsigned long int n)
{
static const unsigned char bitrev[] =
{
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
};
unsigned long int rv = 0;
unsigned char *p = (unsigned char *)&n;
size_t len = sizeof n;
size_t i = 0;
while(i < len)
{
rv <<= 4;
rv = (bitrev[p[i] & 0x0F]);
rv <<= 4;
rv = (bitrev[(p[i++] & 0xF0) >4]);
}
return rv;
}
#define P1 0x4D54D2C3 /* a couple of arbitrarily chosen primes */
#define P2 0x6F7AD887
#define MAX_RAND 32767UL
/* this function messes around with the input for a while, and
then returns a value in the range 0 to MAX_RAND.
*/
unsigned long int gprn(unsigned long int ctr)
{
ctr *= P1;
ctr += P2;
ctr *= ctr;
ctr = bitreverse(ctr);
return ctr % (MAX_RAND + 1);
}
/* inadequate test driver */
int main(void)
{
unsigned long int r = 0;
while(r < 100)
{
printf("%08lX %04lX\n", r, gprn(r));
r++;
}
return 0;
}
The point is that, for any given input, the output of gprn() is always the
same. (It's just a hash of the input, really.) Here, r represents a
position in the PRN stream. So if you have just generated event number 39,
say  which gives 4B0A for the constants I selected for this program  and
then you suddenly decide you need to go back to replay event number 21
(67B1), then you can. If you then want to jump forward in time to event 67
(43F9), that's fine. And whenever you like, you can jump back to event 39,
and you *will* get 4B0A again.
Which is, I think, exactly what you asked for.

Richard Heathfield <http://www.cpax.org.uk>
Email: http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place"  dmr 29 July 1999  
P: n/a

On 20071009 09:48, ki******@gmail.com wrote:
On Oct 9, 4:20 pm, Richard Heathfield <r...@see.sig.invalidwrote:
> kitti...@gmail.com said:
Hi all,
I was wondering if there is a random generator that is "reversible". I
need to go back in time in my application and still need to use
deterministic random numbers. Most of RNG implement the Next function
but what about a Prev ?
Most PRNGs are lossy (in terms of reversibility), relying on a modulo operation to jump around the number space. But why can't you just push each generated number onto a stack? Then you can just pop and reseed whenever you need to go "back in time".
 Richard Heathfield <http://www.cpax.org.uk> Email: http://www. +rjh@ Google users: <http://www.cpax.org.uk/prg/writings/googly.php> "Usenet is a strange place"  dmr 29 July 1999
The problem is that if let's say I have to generate 1000 random in a
sec and need to store 100 min of random, it's not really going to be
good for memory.
For 32bit integers that is about 23MiB, not very much on a modern PC
(though in an embedded system it is a lot).

Erik WikstrĂ¶m  
P: n/a

On Oct 8, 11:49 pm, kitti...@gmail.com wrote:
Hi all,
I was wondering if there is a random generator that is "reversible". I
need to go back in time in my application and still need to use
deterministic random numbers. Most of RNG implement the Next function
but what about a Prev ?
I know I can use an array to store X last values but I'm more
interested to know if it exist something that allows to go backwards.
Also I can't really afford to use the same seed and loop until i get
the previous value.
Yeah. Good cryptography is just a reversable random number generator.  
P: n/a
 ki******@gmail.com wrote:
Hi all,
I was wondering if there is a random generator that is "reversible". I
need to go back in time in my application and still need to use
deterministic random numbers. Most of RNG implement the Next function
but what about a Prev ?
I know I can use an array to store X last values but I'm more
interested to know if it exist something that allows to go backwards.
Also I can't really afford to use the same seed and loop until i get
the previous value.
You don't need to store away the complete pseudorandom sequence. The
standard rand() will repeat it's sequence by srand() for the same seed
value. Hence, if you save away the initial seed and count the number of
rand() calls, you can bruteforce your way forward to the correct
pseudorandom integer again.
<OT>
However, for a long pseudorandom sequence, the bruteforce method will
be inefficient. A simple alternate solution, is then to roll your own
generator:
OWF(seed , n)
There are lots of oneway functions out there, to name a few: MD5,
SHA1, SHA2. The standard encryption algorithms, like DES/AES, can
also be used as OWF.
</OT>

Tor <torust [at] online [dot] no>
CFAQ: http://cfaq.com/  
P: n/a

On Oct 9, 6:12 pm, Richard Heathfield <r...@see.sig.invalidwrote:
kitti...@gmail.com said:
<snip>
I missed something, when you say "you could do something like bit
reversing
the counter and then "mod 32767" it." How would I reverse this ?
You don't. What he's suggesting (and it's a very good idea) is that you
define your own PRNG that is sensitively dependent on an integer counter.
Then, rather than have each number rely on the previous one, you have it
rely *only* on the counter.
So for example, you might do something like this:
#include <stdio.h>
/* this function just reverses the bits in an unsigned long int.
It's a bit wordy, and you can probably crunch it down quite a lot.
*/
unsigned long int bitreverse(unsigned long int n)
{
static const unsigned char bitrev[] =
{
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
};
unsigned long int rv = 0;
unsigned char *p = (unsigned char *)&n;
size_t len = sizeof n;
size_t i = 0;
while(i < len)
{
rv <<= 4;
rv = (bitrev[p[i] & 0x0F]);
rv <<= 4;
rv = (bitrev[(p[i++] & 0xF0) >4]);
}
return rv;
}
#define P1 0x4D54D2C3 /* a couple of arbitrarily chosen primes */
#define P2 0x6F7AD887
#define MAX_RAND 32767UL
/* this function messes around with the input for a while, and
then returns a value in the range 0 to MAX_RAND.
*/
unsigned long int gprn(unsigned long int ctr)
{
ctr *= P1;
ctr += P2;
ctr *= ctr;
ctr = bitreverse(ctr);
return ctr % (MAX_RAND + 1);
}
/* inadequate test driver */
int main(void)
{
unsigned long int r = 0;
while(r < 100)
{
printf("%08lX %04lX\n", r, gprn(r));
r++;
}
return 0;
}
The point is that, for any given input, the output of gprn() is always the
same. (It's just a hash of the input, really.) Here, r represents a
position in the PRN stream. So if you have just generated event number 39,
say  which gives 4B0A for the constants I selected for this program  and
then you suddenly decide you need to go back to replay event number 21
(67B1), then you can. If you then want to jump forward in time to event 67
(43F9), that's fine. And whenever you like, you can jump back to event 39,
and you *will* get 4B0A again.
Which is, I think, exactly what you asked for.

Richard Heathfield <http://www.cpax.org.uk>
Email: http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place"  dmr 29 July 1999
Yes, this exactly what I wanted, thank you very much for help.  
P: n/a

On Oct 9, 6:02 pm, Tor Rustad <tor_rus...@hotmail.comwrote:
kitti...@gmail.com wrote:
Hi all,
I was wondering if there is a random generator that is "reversible". I
need to go back in time in my application and still need to use
deterministic random numbers. Most of RNG implement the Next function
but what about a Prev ?
I know I can use an array to store X last values but I'm more
interested to know if it exist something that allows to go backwards.
Also I can't really afford to use the same seed and loop until i get
the previous value.
You don't need to store away the complete pseudorandom sequence. The
standard rand() will repeat it's sequence by srand() for the same seed
value. Hence, if you save away the initial seed and count the number of
rand() calls, you can bruteforce your way forward to the correct
pseudorandom integer again.
<OT>
However, for a long pseudorandom sequence, the bruteforce method will
be inefficient. A simple alternate solution, is then to roll your own
generator:
OWF(seed , n)
There are lots of oneway functions out there, to name a few: MD5,
SHA1, SHA2. The standard encryption algorithms, like DES/AES, can
also be used as OWF.
</OT>
However isn't that slow? Based on how the original poster described
his/her program as having a feature in it that "goes back in time",
that
doesn't sound like an encryptor to me. If it's something else, speed
might be important, and those algorithms are very complicated and
hence slow. If the RNG does not require security, then they are a
needless complication.

Tor <torust [at] online [dot] no>
CFAQ:http://cfaq.com/  
P: n/a

mike3 wrote:
On Oct 9, 6:02 pm, Tor Rustad <tor_rus...@hotmail.comwrote:
<snip>
><OT> However, for a long pseudorandom sequence, the bruteforce method will be inefficient. A simple alternate solution, is then to roll your own generator:
OWF(seed , n)
There are lots of oneway functions out there, to name a few: MD5, SHA1, SHA2. The standard encryption algorithms, like DES/AES, can also be used as OWF. </OT>
However isn't that slow? Based on how the original poster described
his/her program as having a feature in it that "goes back in time",
that
doesn't sound like an encryptor to me. If it's something else, speed
might be important, and those algorithms are very complicated and
hence slow. If the RNG does not require security, then they are a
needless complication.
MD5 is quite fast, you get 16 bytes output. For security, we rather use
HMAC with SHA2 these days.

Tor <torust [at] online [dot] no>
CFAQ: http://cfaq.com/  
P: n/a

Tor Rustad <to********@hotmail.comwrites:
mike3 wrote:
>On Oct 9, 6:02 pm, Tor Rustad <tor_rus...@hotmail.comwrote:
<snip>
>><OT> A simple alternate solution, is then to roll your own generator:
OWF(seed , n)
There are lots of oneway functions out there, to name a few: MD5, SHA1, SHA2. </OT>
However isn't that slow?
<snip>
>If the RNG does not require security, then they are a needless complication.
MD5 is quite fast, you get 16 bytes output.
Indeed, but it is still 64 rounds of shifting, masking and bit
twiddling. It might add a significant cost to, say, a discrete event
simulation package.
As mike3 points out, the PRNG may not need security. Your idea can
then be adapted by using something much less strong than a oneway
function. For example, any integer hash of seed^n is likely to be
suitable (Knuth suggests simply multiplying by 2654435761 for mod
2**32 numbers). There a lots of others, of course.

Ben.   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 2758
 replies: 14
 date asked: Oct 9 '07
