14 Character Random Number Generator

08/02/2017

In water.c, a poem from my most recent project ./code --poetry I wanted an extremely simple way to produce pseudo random numbers to create the behaviour of raindrops. I found that supposing we have a randomly initialised unsigned 32-bit seed n it is possible to cycle n through pseudo random numbers (in C) using only a 14 character multiplication statement:

n*=0x9e3779b1;

Each time you apply this operation, n will contain a new pseudo random number. Cryptic as it looks, in C this operation is actually a crude hash function for integers called Knuth's multiplicative method, where unsigned integer overflow is used to perform the moduolo operation. And, for any good hash function, repeatedly applying a hash to the result of itself essentially produces a stream of pseudo random values. Of course, this isn't a good hash function, and so repeated application of this hash to itself will quickly deteriorate the quality of the randomness so obviously you shouldn't use this in production code - but it works perfectly well for anything non-critical such as code poetry!

The magic number 0x9e3779b1 is just a large prime number specified in hexadecimal. Technically it could be replaced by any other large number. The most important thing is that it must have few factors, and be large enough to distribute information into the higher value bits when the integer overflows. This particular prime is the closest prime number to 2^32 / phi - the original choice by Knuth.

In water.c I did a couple of additional Bad Things (tm) such as using a 64-bit signed integer and using the uninitialised value as the starting value of the random seed, both of which are undefined behaviour but thankfully gcc was kind enough to produce code for me which still had the effect I was looking for.