Blobs in Games: Upgrading my PRNG for procedural generation

Thursday, May 05, 2022

For a long time now I've been using a very simple Park-Miller LCG random number generator for my procedural generation projects. This is in part because back in the Flash days, Michael Baczynski's "polygonal.de" library was popular, and it had an implementation of Park-Miller. When I switched to Haxe, I used his Haxe data structures library. And then when I switched to Javascript, I used the Javascript port of polygonal's library, and then I wrote my own. I love how simple the core algorithm is.

However I know that it's not a great random number generator.

The original Flash version and the Javascript port both point to Robin Whittle's page about this algorithm, which explained that 16807 was the original multiplier used in this random number generator, but that "47271 or 69621" would be better. I ended up making my own code that used 47271. But I noticed today that the Wikipedia page says 48271 is better, so I'm wondering if 47271 is a typo. So I looked at the paper and indeed, 48271 and 69621 are listed. Not 47271. So for years now I've been using a multiplier based on a typo.

Doh!

[update: 2022-05-06 added description of my goals]

So I started looking around, partly because of this gif of RANDU's output. But what are my goals? I want a seedable generator for procedural genreation projects. I want something that I can run from Javascript, C++, and C#. I want something that lets me save the internal state. I want something small and simple. I want something well-tested.

This page from the author of Alea has several Javascript generators, and talks about Javascript numbers and precision. I had planned to switch to one of these. But I also read bryc's page and decided that I'll use sfc32. Are there any Javascript implementations out there? Well, bryc's page has one! So I don't need to look any further. But I did.

There are libraries like pluggable-prng (sfc32, alea, mulberry32, pcg32) and deterministic-random-sequence (sfc32) and rand-seed (sfc32, mulberry32, xoshiro128ss).

Interstingly, rand-seed and countly-server both have sfc32 code that seems to come from this stackoverflow answer by … bryc. But I tested that code and it doesn't match PractRand's output. It looks like bryc fixed it in this change but didn't update the stackoverflow page. And deterministic-random-sequence's code looks like it's the fixed version of bryc's code. In contrast, pluggable-prng looks like a separate port from PractRand, not using bryc's code. And M.E. O'Neill's implementation also looks like a separate port.

This is my test of the PractRand 0.95 c++ code (this is the original, as Chris Doty-Humphrey wrote PractRand and also sfc; note that earlier versions of PractRand had a different sfc implementation):

typedef unsigned int Uint32;

Uint32 a, b, c, counter;

Uint32 raw32() {
    enum {BARREL_SHIFT = 21, RSHIFT = 9, LSHIFT = 3};
    //good sets include {21,9,3},{15,8,3}; older versions used 
    // {25,8,3} which wasn't as good
    Uint32 tmp = a + b + counter++;
    a = b ^ (b >> RSHIFT);
    b = c + (c << LSHIFT);
    c = ((c << BARREL_SHIFT) | (c >> (32-BARREL_SHIFT))) + tmp;
    return tmp;
}
void seed(unsigned long s) {
    a = 0;//a gets mixed in the slowest
    b = Uint32(s >> 0);
    c = Uint32(s >> 32);
    counter = 1;
    for (int i = 0; i < 12; i++) raw32();//12
}

#include <stdio.h>

int main() {
    seed(12345);
    for (int i = 0; i < 10; i++) {
        printf("%2d: %10u\n", i, raw32());
    }
}

And here's a test of bryc's stackoverflow code:

function sfc32(a, b, c, d) {
    return function() {
        a >>>= 0; b >>>= 0; c >>>= 0; d >>>= 0;
        var t = (a + b) | 0;
        a = b ^ b >>> 9;
        b = c + (c << 3) | 0;
        c = (c << 21 | c >>> 11);
        d = d + 1 | 0;
        t = t + d | 0;
        c = c + t | 0;
        return (t >>> 0) // 4294967296;
    };
}

let R = sfc32(0, 12345, 0, 1);
for (let i = 0; i < 12; i++) R();
for (let i = 0; i < 10; i++) {
    console.log(R());
}

They don't match. Here's a test of bryc's current version:

function sfc32(a, b, c, d) {
    return function() {
        a |= 0; b |= 0; c |= 0; d |= 0; 
        var t = (a + b | 0) + d | 0;
        d = d + 1 | 0;
        a = b ^ b >>> 9;
        b = c + (c << 3) | 0;
        c = c << 21 | c >>> 11;
        c = c + t | 0;
        return (t >>> 0) // 4294967296;
    };
}

let R = sfc32(0, 12345, 0, 1);
for (let i = 0; i < 12; i++) R();
for (let i = 0; i < 10; i++) {
    console.log(R());
}

So I'll use bryc's new version instead of bryc's old version. I don't know if the difference actually matters. Also note that PractRand recommends throwing away the first 12 outputs. Not every version of sfc32 does this.

I also liked JSF and Mulberry32. There are lots of good choices, so how do I choose? Well, I wanted something short and relatively simple, and I decided I was spending too much time on this, so I picked something that PractRand rated highly, and also something that bryc rated highly: sfc32. I think jsf32 or mulberry32 would have been just as good though.

This was a reminder that I often fall into rabbit holes where I spend way too much time learning about something that doesn't matter that much. But it was an interesting diversion, and I ended up with some useful code in this gist.

Labels: math

– Amit – Thursday, May 05, 2022

6 comments:

Scott Turner wrote at May 06, 2022 8:25 AM: Is there some problem with the built-in Javascript random number generator?

I'm using David Bau's seedrandom library (https://github.com/davidbau/seedrandom) because I wanted to be able to seed random numbers for repeatability purposes. (More on seeding here: http://davidbau.com/archives/2010/01/30/random_seeds_coded_hints_and_quintillions.html#more in case you need another rabbit hole.)
Amit wrote at May 06, 2022 11:34 AM: Scott: I should've stated my goals up front. I want a random number generator that's seedable, so I ruled out the built-in one; see this page). And I want one that I can also use in C++ and C# projects, and get the same sequence as in my JS projects. That also ruled out the built-in one. I'll update the blog post.

seedrandom uses alea, which seems like a good choice in js. It looks like it'd be very fast, and it looks pretty simple. But it uses floats! And that scared me a little bit. I'm used to relying on code with integer math but floats scare me a little, especially when trying to be portable between languages and platforms.

The other trouble with alea is that it I couldn't find analysis from random number tests: practrand, testu01, gjrand, etc. Having just discovered that I had the wrong multiplier in an algorithm that was very sensitive to the multiplier, I didn't want to switch to another algorithm that's very sensitive to the multiplier, unless it had been through lots of tests. A lot of the existing test suites are for c code, not js code (see these).
Frank Gennari wrote at May 06, 2022 12:29 PM: If you want more random number generators to test, two of my favorites are in this file:
https://github.com/fegennari/3DWorld/blob/master/src/rand_gen.h

The first was written by Stephen E. Derenzo of UC Berkeley/LBNL and used by their group for scientific purposes in applications such as radio carbon dating where a uniform distribution was essential.

The second one was one I found online written by M.E. O'Neill that's supposedly very good.

I'm not sure how to compare these to the other random number generators you listed, but I would love to know the results.
Amit wrote at May 06, 2022 2:41 PM: Thanks Frank! I should clarify in the post: I am *not* running my own tests of randomness. I'm relying on the tests and recommendations from others:

• bryc's page https://github.com/bryc/code/blob/master/jshash/PRNGs.md
• alea page https://github.com/nquinlan/better-random-numbers-for-javascript-mirror
• PractRand http://pracrand.sourceforge.net/RNG_engines.txt
• M.E. O'Neill's site. https://www.pcg-random.org/posts/some-prng-implementations.html
• John D Cook's blog https://www.johndcook.com/blog/tag/rng/

I think O'Neill's (pcg) sounds very good, and I love the web site, but the code I found was *much* longer than the code for alea (very very short) or sfc32 .

Actually testing them all myself is farther into the rabbit hole than I wanted to go. :-) And visualizations for them like is definitely farther than I wanted to go. I'm going to trust the authors of these other web sites (PractRand in particular) that sfc32 is a reasonable choice.
ator wrote at September 20, 2023 3:52 AM: Having gone down the same rabbit hole myself for a Javascript project, I came out the other end with the Park-Miller PRNG using bigger numbers.

The Park-Miller PRNG only uses 31-bits of state and a multiplier that only needs 48 bits of integer math for calculations. This makes sense in the early 90's when it was most popular, since that can be done on 32-bit machines with a few simple tricks.

If you use doubles, you can use up to 53-bit integer math and can thus increase the number of bits in the state to 35.

seed = seed * 200105 % (2**35 - 31)

And of course if you have access to Javascript's BigInt math you can use those to do the intermediate calculations with more precision and still store 53 bits of state in a plain double.

seed = Number(BigInt(seed) * 5667072534355537n % (2n**53n - 111n))

Source for magic numbers:
https://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-00996-5/S0025-5718-99-00996-5.pdf
bryc wrote at December 14, 2023 11:28 AM: Thanks for documenting your journey in detail, I'm only finding this at random, but I've now updated the sfc32 code in my SO answer... shame no one brought that up, I goofed up there.

In response to @ator:

I would advise extreme caution before using any old-style LCG (Park-Miller is a form of LCG called a MCG). It's easy to mess up and break it. You basically need to be able to interpret randomness tests and compare known constants with custom ones. And it helps to actually understand the math.

LCGs are generally poor in quality (Park-Miller is referred to as minimal standard). You might be able to get away with large 64-bit multipliers and BigInt (speed could be an issue though), but I'd check some posts, and compare results, by these people (what they tend to call the "new" minimal standard:

1. https://www.pcg-random.org/posts/does-it-beat-the-minimal-standard.html
2. https://lemire.me/blog/2019/03/19/the-fastest-conventional-random-number-generator-that-can-pass-big-crush/

But also read the comments in [2].

Anyway, thanks again!