# pseudo-random algorithm allowing O(1) computation of Nth element

It is obvious that using seed value one can easily compute next value of some (deterministic) pseudo-random algorithm - so Nth element can be computed in O(N).

But is there such PRNG that allow to compute Nth element in O(1) while still preserving good periodicity and distribution?

-
I don't understand the question--I am not aware of any PRNG which uses O(N) time to compute the Nth number -- all PRNGs of my acquaintance compute each number in O(1) time. – Igor Rivin Aug 17 '12 at 14:54
@Igor Rivin yes, each next computed in O(1). "N" here is number of value in sequence, i.e. using "seed" we generate 1st value, then 2nd, 3rd, ... Nth. So computing Nth element after existing should take N computations. – John Rivers Aug 17 '12 at 14:57
Would a hash function be what you are looking for? That might depend on what you mean by good periodicity and distribution. – Johan Wästlund Aug 17 '12 at 15:14
@Johan Wästlund well, hash function can be considered as some form of "pseudo-random generator", but usually its not designed to maintain another important properties of PRNG. I don't want to invent wheel here trying to choose hash function which give uniform distribution, so my question about algorithms, especially designed for use as PRNG, but allowing O(1) lookup of some member. – John Rivers Aug 17 '12 at 15:18
@John Rivers: Ah, I see what you mean now. – Igor Rivin Aug 17 '12 at 15:49

I think linear feedback shift registers are examples of what you want. Essentially, these compute powers of $x$ in $F_2[x]/p(x)$ for some polynomial $p(x)$. If $p(x)$ is chosen well, the period can be long. You can compute $x^n$ rapidly by multiplying $c \log n$ terms of the form $x^{2^k}$ which you can compute by repeated squaring.

Of course you will probably want to apply some function to the output to reduce the number of bits and to allow the $n$th value to be $0$ and to equal the $n-1$st value.

-
Can you please recommend any articles about it for "non-scientists"? Wikipedia article about LFSR is not clear enough for me. – John Rivers Aug 18 '12 at 17:11
Apparently people like making LFSRs in Minecraft, but they don't really explain LFSRs. Here is a video which covers some of the basics as part of a class: youtube.com/watch?v=uo4hiP4_HXw Minutes 3-10 may be an elementary introduction to LFSRs before he goes on to other material. Also try maxim-ic.com/app-notes/index.mvp/id/4400 . – Douglas Zare Aug 18 '12 at 18:14

The Numerical Recipes book supplies a specific example of a hash-style generator that is up to scratch as a PRNG. There is a pointer here: http://www.nr.com/forum/showthread.php?t=1653. The principle is simple: you only need a PRNG that is so thorough that the values generated by seed,seed+1,seed+2,.. are acceptably random. You can view the code (for free) in section 7.1.4 of the online version of the 3rd edition (via http://www.nr.com), and more importantly the discussion about what qualifies as "up to scratch". The code amounts to the following:

#include <stdio.h>
#include <inttypes.h>
/* I used http://stackoverflow.com/questions/2844/
* how-do-you-printf-an-unsigned-long-long-int
* for advice on uint64_t PRIu64 and inttypes.h */

uint64_t
ranhash(uint64_t v) {
v *= 3935559000370003845LL;
v += 2691343689449507681LL;
v ^= v >> 21; v ^= v << 37; v ^= v >> 4;
v *= 4768777513237032717LL;
v ^= v << 20; v ^= v >> 41; v ^= v << 5;
return v;
}

double
ranhashdoub(uint64_t v) {
return 5.42101086242752217E-20 * ranhash(v);
}

int
main(int argc, char*argv[])
{
uint64_t seed = 0; /* same results every time */
long j;
for(j=0; j<10; j++)
printf("%"PRIu64"\n",ranhash(seed++));
return 0;
}

-