Objective

How we can we leverage pseudo random number generators to our benefit.

Setup

Perhaps you want to generate one of these lovely tiles Or generate the following string

bAjFcOcLbMnBfKaHgIeNmGcDpEaJhChPmAaFfObLmMeBiKpHbIlNpGbDkEhJkCgPhAhFiOaLhMlBlKoHmIcNcGaDfEoJnCfPcAoFlOpLcMcBoKnHhIjNfGpDaEfJaCePnAfFoOoLnMjBbKmHcIaNiGoDlEmJdCdPiAmFbOnLiMaBeKlHnIhNlGnDgEdJgCcPdAdFeOmLdMhBhKkHiIoNoGmDbEkJjCbPoAkFhOlLoMoBkKjHdIfNbGlDmEbJmCaPjAbFkOkLjMfBnKiHoImNeGkDhEiJpCpPeAiFnOjLeMmBaKhHjIdNhGjDcEpJcCoPpApFaOiLpMdBdKgHeIkNkGiDnEgJfCnPkAgFdOhLkMkBgKfHpIbNnGhDiEnJiCmPfAnFgOgLfMbBjKeHkIiNaGgDdEeJlClPaAeFjOfLaMiBmKdHfIpNdGfDoElJoCkPlAlFmOeLlMpBpKcHaIgNgGeDjEcJbCjPgAcFpOdLgMgBcKbHlInNjGdDeEjJeCiP

...but we only have 4 bytes of data to transmit it with. Both examples shown were generated with those exact constraints.

We use the term pseudo but we might as well drop it. The fact of the matter is that there is no such thing as true random outside of the quantum world. If we have enough information on pretty much any system we could predict its outcome. This includes Math.random() or atmospheric noise (Granted one is ALOT more difficult to predict)

For the sake of simplicity we will also just show the formula we need to use to generate our sequence. We will also accompany that formula with some suggested parameters in order to achieve the "best" results. We will be using Linear Congruential Generators (Hereon referred to as LCG) and the parameter choice is based on Hull–Dobell theorem. Please refer to the references section to see other possible choices of parameters and their implications to our generated sequence.

Formula

\(X_{n+1} = (aX_n + c) \equiv mod\hspace{1mm}m\)

Parameters

• \(X_0\) - This is our seed value. \(0 \le X_0 \lt m\)
• \(c\) - Our shifter. \( c = 2N + 1 \)
• \(a\) - Our multiplier. \(a = 4N + 1\)
• \(m\) - Our modulo. \(m = 2^N\)

Its good to note that our generated sequence is guaranteed to be a unique sequence of m elements that will appear to be random to someone who doesn't know our choice of params.

\([X_0, (aX_0 + c)mod\hspace{1mm}m, ... X_m]\)

Use Case

So how can we actually use it? Below are some ideas to hopefully inspire you.

Generating Unique Ids

Since our sequence is unique we can extract unique subsequences. These unique subsequences can also be mapped to integer values for even more convenience. By holding our m, a & c variables constant, we could supply any valid seed and generate a unique subsequence which can then be converted to a string to create our own UID generator.

In this example, we are are using parts of our sequence to generate unique ids, tags, arrays, etc...

Generating Unique Data

The tile images I showed earlier were generated using LCG. While not too interesting to look at, in a system with the right constraints we could generate some interesting run-time data (See section on Simcity for a real world example). For the tiles I generated, I defined my sequence with 4 bytes, 1 byte each for m, a, c & our seed value. This generated a unique sequence of length 256 (hence the title name)

In this example, we are using our entire sequence to greatly minimize the amount of data that needs to be transmitted when we are generating content on the fly. While my example turned 4 bytes of data into 256. By using 16 bytes of data, we could transmit a sequence with over 17 gb worth of "data"

Its important call out is that while i refer to this as data, we can't actually encode meaningful data with these sequences but we can make meaning out of the sequence we return.

Simcity SNES

A good example for the above would be the maps generated in SimCity for the SNES. SNES cartridges held 4mb of data at most. But there were 1000 maps! in the game, each with 12000 tiles. Assuming they could of packed each tile into 2 bits worth of data, storing all the maps would of consumed 3mb leaving very little left over for graphics, sound, and code.

Extra

If you are curious to see how parameter choice affects the frequency and spread of our elements generated. Play below with a small tool I created for demonstration purposes.

References

en.wikipedia.org/wiki/Linear_congruential_g.. chagall.med.cornell.edu/BioinfoCourse/PDFs/..