The Myth of Noise

Let’s step back for a moment.

There’s an ongoing problem among engineers today, and it’s an understandable problem. We like to think that our actions are always based on the foresight of science, but the truth is, operationally, we’re very independent of the empirical method. For us, it just has to look like it works; the semantics of how, while legitimately interesting, are not bringing our paychecks any closer.

This is… acceptable, though flawed. Engineers are much closer to artists than scientific researchers; we create. We love science, but we don’t always have all the answers, and a lot of the time, neither does everyone else. What’s worse, sometimes having scientific correctness is prohibitively expensive compared to having a passable result.

Not that scientific programming can’t be a thrill in itself…

So, that brings me to “noise”. There is a persistent myth among software engineers that noise is truly random, or if not that it is truly random, the notion that it can be truly random. Both are amateurish bull-pucky. Noise is extremely comprehensible, and I dare say it even feels like a cheat.

Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.

John Von Neumann

Computers are entirely deterministic by design. Any function can be broken down into a collection of pure functions, for which the same input will always result in the same output.

We do have <random.h> and any number of other psuedorandom—and that psuedo– is the important part—number generators, though. So how do they work? There are a lot of ways that they can work, but I’m going to start with the most common, the linear congruential generator, or LCG.

LCGs require only a seed value, which, in entertainment, is typically the time. They have an internal state, after receiving that seed value, every value returned by them is a new and reasonably difficult to predict—at least for entertainment purposes—number. How they operate internally is painfully (and arguably beautifully) simple.

You see, every single LCG can be broken down to the same formula:

X_{n+1}=(a X_n + c) mod m
The LCG Formula

I get that this may look complicated to some, but it’s blissfully not. Borrowing LaTeX notation, which should be clear enough to most, X_{n+1} is our returned value, that’s the new random number X_n, on the other hand, is the last random number generated. That is, it is the internal state.

It might also be the seed value.

The remaining important factors are a, c, and m, namely the multiplier, increment, and modulus. For some, that mod function might look a little weird, but it’s just the modulus function, which is very similar to a remainder. (There are a few minor differences involving negative numbers, but I’m not going to bore you with the details here. Maybe in another blog post someday.)

To clarify, if A is three and B is two, then A mod B would be one— because three divided by two is one, remainder one. That’s almost all that modulus is, which is thankfully very easy for machines to do.

If we take this, and set our multiplier a to 214,013, and increment c to 2,531,011, and lastly our modulus m to 2³², then we’ve got the equivalent of Visual C++’s random number generator. There are plenty of alternatives to this, too. Most of them are even listed on Wikipedia—this knowledge isn’t as arcane as people like to think.

Incidentally, this is a huge problem for cryptography, as time itself is not random. It’s quite predictable. So, you wouldn’t want a system limited to an LCG to encode, say, bank account information, if it’s seeded with the time. Thankfully this isn’t a problem for entertainment purposes, as it’s still virtually impossible to take a small set of results and back-calculate the formula that produced them.

Additionally, it is very easy to pick a bad set of factors for an LCG. There’s a lot of wonderful math behind them, which for space constraints I’m not going to go into here; but any time you’re looking at a cheap algorithm for generating white noise, you’re likely to be using an LCG.

Feel free to implement one in Python right now—it isn’t any harder than it looks.

For companies and devices that need “true” random numbers, it’s typical for an external unpredictable phenomenon to be used. I’m hesitant to use the word “random” here, as a guy who got his beginning in physics, as our universe, complicated as it may be, is still deterministic.

To illustrate this, the company Cloudflare famously uses a video of a wall of lava lamps to seed its encryption, as they’re much more difficult to predict. For *nix-based computers (really anything using Udev), there’s typically a cache of real “random” data pulled from system temperature, keystroke frequency, and any number of other elements outside of system control, which can be used to generate a cryptographically secure value.

While these elements are virtually impossible to determine from the outside, they are the result of physical (albeit often chaotic) processes, with their own impulses and mechanisms controlling them. (Contrary to popular belief, even quantum mechanics is not truly “random”; it simply fragments perception of values into unknowable facets; there are still rules.)

So what do we really mean by “random”? Most commonly, we’re looking for data which is difficult to predict. A good LCG does this. For cases where LCGs aren’t enough, there are a number of derivatives, including inversive congruential generators (where the multiplier is divided by the previous result), and permuted contruential generators (which multiply the result by a curve which makes them better-behaved statistically), among others.

Like so many things, it ultimately comes down to what you’re trying to do with it, and what will be passable for your purposes. You are unlikely to ever experience true noise, only mystery!

Published by Michael Macha

I'm a game developer for both mobile and PC. My education is in physics, journalism, and neuroscience. Founder and CEO of Frontier Medicine Entertainment, located in the beautiful city of Santa Fe, New Mexico.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: