(e-mail address removed) 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
& 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
