Question

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?

Answer 1

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.

Answer 2

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;
}