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?

  • $\begingroup$ 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. $\endgroup$ – Igor Rivin Aug 17 '12 at 14:54
  • 2
    $\begingroup$ @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. $\endgroup$ – John Rivers Aug 17 '12 at 14:57
  • $\begingroup$ Would a hash function be what you are looking for? That might depend on what you mean by good periodicity and distribution. $\endgroup$ – Johan Wästlund Aug 17 '12 at 15:14
  • $\begingroup$ @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. $\endgroup$ – John Rivers Aug 17 '12 at 15:18
  • $\begingroup$ @John Rivers: Ah, I see what you mean now. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Can you please recommend any articles about it for "non-scientists"? Wikipedia article about LFSR is not clear enough for me. $\endgroup$ – John Rivers Aug 18 '12 at 17:11
  • $\begingroup$ 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 . $\endgroup$ – 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 */

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;

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

main(int argc, char*argv[])
  uint64_t seed = 0; /* same results every time */
  long j;
  for(j=0; j<10; j++)
  return 0;
| cite | improve this answer | |

FWIW: any reasonably-secure block cipher in CTR mode is a supposedly-perfect PRNG (if it is not - for about 20 years now, such cipher is not considered secure).

How to calculate nth element of PRNG using this method:

-- in advance, once --

  • choose cipher C (ranging from rather poor XXTEA to rather secure Chacha20 and AES) and generate some random key K for it (it has to be done once, so K can be taken from random.org or something)

-- to calculate nth element --

1) take number n and copy it into input_block for the cipher C (filling the gaps as necessary)

2) encrypt input_block with cipher C and key K. Output is supposed to be perfectly-random.

Pros: (a) secure, which translates into (b) the best-quality RNG out there (any kind of correlation is a severe security weakness, and lots of effort is spent on this kind of analysis).

Cons: performance is lower than for other PRNGs (though on a single core good implementation can easily reach gigabytes/second).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.