Linear Congruent Insufficiency: A First Pass at Randomness for PETI

Last Updated: 2022-11-29 06:30:00 -0600

Last week in our quarterly update post I mentioned implementing a Mersenne Twister for PETI. This was a bald-faced lie, made possible by not consulting my notes. A Mersenne Twister would have been much more effective than the Linear Congruential Generator I implemented instead. I want to talk about how we got there, as well as what is wrong with it.

This Ain’t That: A Note on LCGs and their Usage

A Linear Congruential Generator (LCG) is basically just a forumla (and a method of employing that formula) for generating pseudorandom numbers. It’s an old and well-known method of doing this; however, even high-quality LCGs were recently revealed to have a very interesting flaw that I don’t have the mathematics experience to explain clearly.

LCGs were an extremely popular way, in the early days of games consoles and personal computing, to give your average user access to “random enough” outputs. The math, which is quite straightforward and explained in more depth [here], is fine in terms of generating a relatively small number of random numbers, and it’s lightweight enough to run quickly. With outputs used appropriately, you’re going to be “more random” than a human user could reasonably be expected to account for. (Leave aside for the moment the issue of speedrunners manipulating game system RNGs based on flaws in the design. I’ve used such techniques myself; they’re actually fairly easy to learn to do in many videogames).

What an LCG in general - and especially THIS LCG - is not appropriate for is cryptographic applications. If you need a source of randomness for secrecy and privacy preservation, this is very much not even close to the technology you want. This is marginally more secure than pushing random keys on your keyboard. In other words, it is not actually meaningfully random.

Wait, there’s flavours of random?

Indeed there are. In the case of an LCG, the largest flaw in the randomness of the LCG is that LCGs have a low period in their output and that they can have a noticable relationship between successive calls of the function. This is true for a few reasons:

For a given previous result or seed, the current result is predictable if the constraints of the generator are known.
The modulus, one of the parameters of the generator, almost directly sets the period of the generator, which can never exceed the multiplier. Heck, if the multiplier is a power of two, the period will be as little as m/4!

These things both sound like they’d doom the use of an LCG, but again, for low-stakes gaming applications they’re actually plenty random. All of the factors that control the generator, from initial seed to multiplier, modulus, and increment, are under developer control. If the hardware permits you can choose a sufficiently large modulus and an appropriate multiplier to maximize the amount of the modulus’s permitted space that your state can occupy.

While this relatonship between all rolls of the proverbial dice presents a problem when high-quality-randomness is needed, it’s not a problem in gaming, in part because you can hide the die rolls; more on that in a moment.

Why this at all then?

For the same reasons that LCGs were popular in the first place: on the heavily-constrained PETI hardware, running an LCG remains a relatively clean and trivial operation. The RNG state itself is stored in a single float worth of memory and the formula for the transformation fits handily on one line. Indeed, we added a roll of the RNG before every rendered frame of output and no delay in gameplay is noticable by a human.

In fact, the LCG was the simplest part of the process of implementation. Seeding, discussed below, was a much harder prospect as was the way we handled the output. Both, I suspect, qualify as “the problem”.

So, what’s the problem?

Well, the problem is pretty simple really: when monitoring the output of the RNG using a special function written to simply print that output to the display, it has a remarkably low period - on most boots, roughly eight to fifteen rolls. Given that a hard-to-predict number of rolls may occur between any given human inputs on the device, that’s still not necessarily predictable, but it’s poor enough that I want to investigate and fix it.

To my mind, there’s only three real places the problem can be, which I’m listing in order of what I feel is likely the most to least problematic:

The “Draw Float” function sucks. The RNG function that returns a 0/1-bounded float for the purposes of making decisions using the RNG does the world’s laziest version of normallizing and bounding that output, by simply dividing by 0xFFFFFFFF. This exaggerates the periodicity of the RNG two ways:
- We now have an even smaller space in which the random output can land, and;
- We include the least significant bits of the RNG output, which have a lower period AND are weighted more heavily in a division operation.
There is a flaw in how I generate the initial seed. Since all of the randomness in an LCG comes from the very first value you feed it (the initial seed), I chose a relatively untidy method of coming up with that number. On the MSP430FR5994, TI has included a very large (iirc, 128-bit) random number in a write-only section of memory. I implemented a function to grab a random word out of that large number to act as my initial seed. There’s just one problem - 9 times in 10, that function always grabs the same word. There’s something wrong with how we’ve implemented reading the Analog-Digital Converter (ADC); it’s probably not as noisy as I would like. This isn’t going to be directly responsible for the period problem, but it is lowering the quality of the randomness and fixing it would solve the period problem indirectly.
The LCG parameters may be set wrong. I have a modulus just shy of 2^32, much higher than my actuial period. What’s likely at issue then is that both the increment and the multiplier parameters are set to less-than-ideal states. If we solve for the normalizing function and the results are still highly periodic, experimenting with these values may improve the output.

So What Are We Going To Do About It?

I’m so glad you asked! We do what you always do with software problems - patch them. I have a lab stream scheduled for Thursday, December 1, 2022 at 2230 UTC to go over this. I’d like to fix it soon, immediately in fact, ideally before we start developing any of the gameplay functions that lean on the LCG.

And if we get a good result early in that stream, we’ll work on finishing the new back-board layouts I talked about in [the last update] as well. If you’ve never been to a lab stream before, you should come along. There’ll be chiptune music, and tea, and we’ll have a nice chat.

If you wanted to show your support financially, for free tools and toys like Pyminder, Tapestry, and PETI, your best avenue is via my Github Sponsors account or by making a one-time donation to Arcana Labs via Ko-Fi.com or through other avenues detailed here. Supporters also get access to a special patrons-only section of the Arcana Labs Discord Server as well, and new bonuses are soon to be introduced on the github side!