Check out Random123, an implementation of counter-based random number generators.  It won best-of-conference at the ACM Supercomputing &#x27;11 conference.<p>Basically the idea is that you have a seed which is used as an encryption key, and then you encrypt a counter value to produce an output.  Using the next counter value represents the second output from the generator, and so forth.  Different seeds produce different output sequences.  If you accept that the encryption algorithm works properly, then the output is uncorrelated for a given counter sequence or seed sequence (although seed sequences are slightly less random than counter sequences).<p>You don&#x27;t need to store state, and you can seek to an arbitrary position in the PRNG stream in O(1) time simply by recomputing the output for the desired counter value.  For non-cryptographic applications, you can derive the seed value from some unique property of your dataset (eg id number of an item being operated upon) and then you don&#x27;t even need to explicitly store the key value.<p>On AES-NI compatible hardware the cryptographically strong varients outperform even crushable PRNGs like Mersenne Twister.  These are a fantastic choice where you have that acceleration.  Your computer is built to do it really fast, and this lets you utilize that.<p>They also offer non-cryptographic but crush-resistant variants that roughly double that performance.  These algorithms parallelize really well and those advantages are even more significant on GPUs, where memory is at a premium and cryptographic acceleration is usually not available.<p><a href="http:&#x2F;&#x2F;www.thesalmons.org&#x2F;john&#x2F;random123&#x2F;papers&#x2F;random123sc11.pdf" rel="nofollow">http:&#x2F;&#x2F;www.thesalmons.org&#x2F;john&#x2F;random123&#x2F;papers&#x2F;random123sc1...</a><p><a href="http:&#x2F;&#x2F;www.thesalmons.org&#x2F;john&#x2F;random123&#x2F;releases&#x2F;1.06&#x2F;docs&#x2F;" rel="nofollow">http:&#x2F;&#x2F;www.thesalmons.org&#x2F;john&#x2F;random123&#x2F;releases&#x2F;1.06&#x2F;docs&#x2F;</a>