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 32bit 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 noncritical 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
64bit 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.