1. 7

  2. 5

    The random here is pretty pseudo. That’s not necessarily bad, but this is definitely more “permutation of unique numbers” than random. Seeing one number allows you to predict the entire rest of the sequence.

    The link to the OpenBSD rng is rather old (and rc4 definitely repeats before its period expires), but using a block cipher like AES in counter mode will get you a sequence of (128 bit) numbers that don’t repeat and are completely random. If you must have smaller numbers, this probably requires cutting the block size down to fit.

    1. 4

      I realize this is an old post and I’m not responding to the author..

      TestU01 SmallCrush is pretty much useless. It is trivial to beat with an rng that has obvious flaws. About the only thing it can help you quickly detect is a complete failure (e.g. caused by a typo or other bug that makes the rng behave not-as-intended.)

      I recently wrote a little prng (which I christened angersock) that passes smallcrush, crush, bigcrush, and all the dieharder tests. Unless you increase the rounds count, it’s still quite possible to visually observe anomalies if you take successive pairs and plot them to an image. As with crypto, you can improve the output by doing more rounds.

      I’m not sure what’s the grand insight to be gained from this post, but if you’re looking into making prngs, these one-to-one maps are probably the best starting point. They guarantee uniformity when the entire period is observed, and for simple small-state generators whose last output is the starting state for the next output, they guarantee maximal period with no loops. Whether you’re making a non-repeating rng or not, these guarantees are really nice to have. And you can trivially turn such an rng into one with repeats by simply returning only a part of the output to the caller.

      EDIT: Seeing that the author uses his rng to generate unique keys to for a benchmark of judy arrays and a hash table, I think he could’ve just taken the full state of a linear congruential generator. The low bits are embarrassingly periodic, but that probably doesn’t matter in the given scenario. If it did, a rotate and perhaps a single multiply ought to be enough to make it good. The quality of randomness doesn’t seem significant here, as long as the distribution is uniform enough.