Synchronizing randomness across Pixelblazes

I just posted a new pattern, “Synchronized Random Numbers” to the community patterns. You can copy and paste out of it the definition of prng, a simple random number generator with a deterministic seed. This lets you have “randomness” synchronized across a fleet of Pixelblazes in case you still want them to be able to match. The implementation is very careful to avoid overflow and should be able to output values in [0, 2^16)

// ---- PRNG ---- //

// Modular addition which avoids overflow.  Uses the identity
// (a + b) % mod = (a % mod) + (b % mod) % mod
function addmod(a, b, mod) {
  var am = a % mod;
  var bm = b % mod;
  
  // If `mod`, `a`, and `b` are very large, just returning `(am + bm) % mod` could overflow
  var diff = mod - bm;
  if (diff <= am) { // aka if (am + bm >= mod)
    // Since am < mod and bm < mod, am + bm < 2 * mod.  In this specific case mod < am + bm < 2 * mod,
    // so we have the identity am + bm % mod = am - mod + bm
    return am - diff;
  }
  return am + bm;
}

// modular multiplication which avoids overflow.  Takes O(log(a)) iterations.
function mulmod(a, b, mod) {
  var res = 0;
  if (b == 0) return 0;
  while (a != 0) {
    if (a & 1) {
      res = addmod(res, b, mod);
    }
    a >>= 1;
    b = addmod(b, b, mod);
  }
  return res;
}

// This is the BSD rand() from https://rosettacode.org/wiki/Linear_congruential_generator.
// The value of `a` has been expressed mod 2^16.

export var prng_state = 0;
var mod = pow(2, 16);
function prng(max) {
  prng_state = addmod(mulmod(20077, prng_state, mod), 12345, mod);
  return prng_state / mod * max;
}

// ---- END PRNG ---- //

Note that this version has some bugfixes and some cleanup from the one posted on the Patterns page. I’m not sure how to take down and re-post a pattern.

2 Likes

If you post an epe file here I can update it.

1 Like

Synchronized Random Numbers (3).epe (8.2 KB)

1 Like

Thinking about it, I guess really this post is also a request for a randomSeed(seed) function which would let us accomplish the same thing using the proper RNG Pixelblaze already has with it

Right now random in Pixelblaze is a true random number generator, or more accurately a PRNG periodically seeded by true random bits.

I think a seedable PRNG would be a nice API to add, especially if speed was essential. Perhaps along with noise functions.

(Edit 9 months later: A seedable PRNG has now been introduced as prng(seed) in firmware 3.30. Here’s the release announcement)

1 Like

Yeah, Gaussian noise and colored noises and maybe even Perlin noise could be cool.

Out of curiosity what is the entropy source for the seed?

https://docs.espressif.com/projects/esp-idf/en/latest/esp32/api-reference/system/random.html

1 Like