Joss Knight

2004-08-21 17:23:41 UTC

Permalink

I am looking for a pseudo-random number generator which allowsRaw Message

efficient random access. I'm not interested in good statistical

properties or an enormously long cycle length, as long as the sequence

appears random (to the eye).

On this group I found an old article concerning the ZIP algorithm,

which is supposedly indexable:

x_i = (2 ^ (i * (p - |p| - 1))) mod p, where |p| is the number of

binary bits of p

at

http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&threadm=3m39hc%2444d%40net.auckland.ac.nz&rnum=31&prev=/groups%3Fq%3D%2522random%2Bnumber%2Bgenerator%2522%2B%2522random%2Baccess%2522%26start%3D30%26hl%3Den%26lr%3D%26ie%3DUTF-8%26selm%3D3m39hc%252444d%2540net.auckland.ac.nz%26rnum%3D31

Problem is, p is both a magic number and defines the cycle length, and

my length needs to be at least several thousand, so (i * (p - |p| -

1)) is very large. I'm not savvy enough to know how to implement this

efficiently. Memory efficiency is also important here, so I can't

afford to hold 2^100000000, or whatever, in memory, even if I knew how

to implement the mod operator for a large block of memory representing

a single integer (in C, for instance), which I don't. This just isn't

my field!

On the link there are implementations of the recursive version of this

algorithm, but if anyone knows how to implement the indexed version,

or knows of other efficient random-access PRNGs, I'd really like to

know about it. I cannot do this by pregenerating a long sequence, for

my application.

Cheers,

Dr Joss Knight

[Probably sci.crypt.research is not exactly the right place for

this kind of question, if you don't need any kind of cryptographic

properties. But, take a look at linear congruential or LFSR generators;

they both permit fast random access to any index in the stream. --DW]