Skip to content

Instantly share code, notes, and snippets.

@tripzilch
Created January 31, 2016 22:19
Show Gist options
  • Save tripzilch/691a0be04920b6b83cda to your computer and use it in GitHub Desktop.
Save tripzilch/691a0be04920b6b83cda to your computer and use it in GitHub Desktop.

Some quick notes about PRNGs

If the docs don't specify the cycle length, IMHO better not use it in situations where it matters.

65**5 is about 30 bits. if the PRNG-state is 32 bits, and the PRNG algorithm doesn't cycle through the full state, that may already be too little.

In many languages the default PRNG is implemented as a LCG, which are just 2-3 lines of code, and just not very good on their own. Computational science has found much, much better algorithms that are (almost) just as tiny to implement. Maybe 4-5 lines, see PCG-random.org.

I recently used a Java port of CMWC4096 from StackOverflow, for a numerical simulation in Java (where the default Math.random() has a stupid-bad cycle length, and the Java crypto-PRNG might have been too slow). It worked great. Not quite as tiny as PCG-random, but still short and it was ready-to-use Java-code that fit my needs.

For your use-case, however, if Node has a nice cryptographically-secure PRNG in its default libs, I'd go for that. You still need to check the cycle-length and how many bits the CSPRNG has, but if it's supposed to be believably cryptographically secure, that should be in the specs :) Likely to be more than enough (because brute-force). And a CSPRNG promises a couple of other things (in fact it promises nearly everything that a PRNG could wish for) which may or may not bite you in the ass in the future, but are good to just not have to worry about.

The speed of a CSPRNG is (I read somewhere, but you can easily test it) about 20-100x slower than a simple LCG. This is still absolutely and sufficiently crazy-fast for UUID purposes and you should not have to worry about that at all.

There's really something to be said for it that the default PRNG in any language should be a CSPRNG with a huge cycle by default (but afaik currently it almost never is), because the only point when speed could become an issue is when you're running big numerical simulations, in which case it's easy to notice and switch to a more performant PRNG. The converse case, using a bad PRNG for non-numerical purposes is much harder to notice, unless the programmer already knows that default PRNGs are a minefield of obscure bugs :)

If you like to read more theory about PRNG-qualities and such, I found the paper on the PCG-random site surprisingly accessible to read. Explains the requirements and pitfalls quite well, IMO.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment