Reversible random generator ?

[kittikun]

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 !

[Richard Heathfield]

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 re-seed
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

[robertwessel2]

On Oct 9, 1:49 am, [e-mail] 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.

[kittikun]

On Oct 9, 4:20 pm, Richard Heathfield <[e-mail]:

[e-mail] 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 re-seed
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.

[kittikun]

On Oct 9, 4:22 pm, "[e-mail]" <[e-mail]>
wrote:

On Oct 9, 1:49 am, [e-mail] 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.

[kittikun]

On Oct 9, 4:49 pm, [e-mail] wrote:

On Oct 9, 4:22 pm, "[e-mail]" <[e-mail]>
wrote:

On Oct 9, 1:49 am, [e-mail] 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 ?

[kittikun]

On Oct 9, 5:23 pm, [e-mail] wrote:

On Oct 9, 4:49 pm, [e-mail] wrote:

On Oct 9, 4:22 pm, "[e-mail]" <[e-mail]>
wrote:

On Oct 9, 1:49 am, [e-mail] 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

[Richard Heathfield]

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

[=?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=]

On 2007-10-09 09:48, ki******@gmail.com wrote:

On Oct 9, 4:20 pm, Richard Heathfield <[e-mail]:

> [e-mail] 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 re-seed
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 32-bit integers that is about 23MiB, not very much on a modern PC
(though in an embedded system it is a lot).

--
Erik Wikström

[Michael Angelo Ravera]

On Oct 8, 11:49 pm, [e-mail] 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.

[Tor Rustad]

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 pseudo-random 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 brute-force your way forward to the correct
pseudo-random integer again.

<OT>
However, for a long pseudo-random sequence, the brute-force method will
be inefficient. A simple alternate solution, is then to roll your own
generator:

OWF(seed , n)

There are lots of one-way functions out there, to name a few: MD5,
SHA-1, SHA-2. The standard encryption algorithms, like DES/AES, can
also be used as OWF.
</OT>

--
Tor <torust [at] online [dot] no>

C-FAQ: http://c-faq.com/

[kittikun]

On Oct 9, 6:12 pm, Richard Heathfield <[e-mail]:

[e-mail] 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.

[mike3]

On Oct 9, 6:02 pm, Tor Rustad <[e-mail]:

[e-mail] 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 pseudo-random 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 brute-force your way forward to the correct
pseudo-random integer again.

<OT>
However, for a long pseudo-random sequence, the brute-force method will
be inefficient. A simple alternate solution, is then to roll your own
generator:

OWF(seed , n)

There are lots of one-way functions out there, to name a few: MD5,
SHA-1, SHA-2. 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>

C-FAQ:http://c-faq.com/

[Tor Rustad]

mike3 wrote:

On Oct 9, 6:02 pm, Tor Rustad <[e-mail]:

<snip>

><OT>
However, for a long pseudo-random sequence, the brute-force method will
be inefficient. A simple alternate solution, is then to roll your own
generator:

OWF(seed , n)

There are lots of one-way functions out there, to name a few: MD5,
SHA-1, SHA-2. 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 SHA-2 these days.

--
Tor <torust [at] online [dot] no>

C-FAQ: http://c-faq.com/

[Ben Bacarisse]

Tor Rustad <to********@hotmail.comwrites:

mike3 wrote:

>On Oct 9, 6:02 pm, Tor Rustad <[e-mail]:

<snip>

>><OT>
A simple alternate solution, is then to roll your own generator:

OWF(seed , n)

There are lots of one-way functions out there, to name a few: MD5,
SHA-1, SHA-2.
</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 one-way
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.