5
\$\begingroup\$

So I need a PRNG in Python and JavaScript that yields the same results, which is the reason I can't use the built-in methods. It doesn't have to be very good or even cryptographically secure, since it's only for generating mock data for tests.

The algorithm used is the very short one by George Marsaglia described here.

The Python version:

import typing


class SimpleRandom:
    def __init__(self, seed: int = 0):
        if seed < 0 or seed >= 2**32 - 2:
            raise ValueError("seed must be between 0 and 2^32 - 3")
        self.mz = seed + 1
        self.mw = seed + 2

    def next(self) -> int:
        self.mz = (36969 * (self.mz & 65535) + (self.mz >> 16)) % 2**32
        self.mw = (18000 * (self.mw & 65535) + (self.mw >> 16)) % 2**32
        return ((self.mz << 16) % 2**32 + self.mw) % 2**32

    def randrange(self, start: int, stop: int) -> int:
        if start >= stop:
            raise ValueError("start must be less than stop")
        if start < 0 or stop < 0:
            raise ValueError("both start and stop must be positive")
        if stop - start > 2**32:
            raise ValueError("stop - start must be less than 2^32")
        return self.next() % (stop - start) + start

    def choice(self, seq: typing.Sequence) -> typing.Any:
        return seq[self.randrange(0, len(seq))]

    def choices(self, seq: typing.Sequence, k: int) -> typing.Sequence:
        return [self.choice(seq) for i in range(k)]


if __name__ == "__main__":
    random = SimpleRandom(0)

    print(f"First random integer: {random.next()}")

    for i in range(10000):
        random.next()

    print(f"Random int after 10000 calls: {random.next()}")
    print(f"Random int 1000 <= {random.randrange(1000, 2000)} < 2000")

    arr = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]

    print(f"Random choice from a-j: {random.choice(arr)}")
    print(f"Random choices from a-j: {', '.join(random.choices(arr, 7))}")

And the JavaScript version:

function SimpleRandom (seed = 0) {
  if (seed < 0 || seed > 0xffffffff - 2) throw new Error('seed must be between 0 and 2^32 - 3')
  this.mz = seed + 1
  this.mw = seed + 2
  this.next = function () {
    this.mz = 36969 * (this.mz & 65535) + (this.mz >>> 16)
    this.mw = 18000 * (this.mw & 65535) + (this.mw >>> 16)
    return ((this.mz << 16) + this.mw) >>> 0
  }
  this.randRange = function (min, max) {
    if (min === max) return min
    if (min > max) throw new Error('min > max')
    if (max - min > 0xffffffff) throw new Error('Range too large')
    return min + (this.next() % (max - min))
  }
  this.choice = function (arr) {
    return arr[this.randRange(0, arr.length)]
  }
  this.choices = function (arr, k) {
    if (!Number.isInteger(k) || k < 0) throw new Error('k must be a positive integer')
    if (!Array.isArray(arr)) throw new Error('arr must be an array')
    const result = []
    for (let i = 0; i < k; i++) {
      result.push(this.choice(arr))
    }
    return result
  }
}

if (require.main === module) {
  const random = new SimpleRandom(0)
  console.log(`First random integer: ${random.next()}`)
  for (let i = 0; i < 10000; i++) {
    random.next()
  }
  console.log(`Random int after 10000 calls: ${random.next()}`)
  console.log(`Random int 1000 <= ${random.randRange(1000, 2000)} < 2000`)
  const arr = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
  console.log(`Random choice from a-j: ${random.choice(arr)}`)
  console.log(`Random choices from a-j: ${random.choices(arr, 7).join(', ')}`)
}
\$\endgroup\$
5
  • \$\begingroup\$ Why must you re-implement the algorithm in two places? Can you not set up some kind of serialized value-passing scheme where both contexts have access to the same data? Can you describe these contexts in more detail, especially, why they're in different languages? \$\endgroup\$
    – Reinderien
    Commented Jan 18 at 19:15
  • \$\begingroup\$ @Reinderien Part of a Docker architecture, two micro-services (one Python, one NodeJS). NodeJS is generally used, but in rare cases Python because of important libraries that aren't available in NodeJS. I know this is BAD. And it is correct that I could serialize the data and exchange it, but then I need shared volumes or implement a special endpoint ... do I really want to implement that just to exchange mock data? Of course that implementing that algorithm twice turned out to be not as trivial as I assumed. \$\endgroup\$
    – Amaterasu
    Commented Jan 18 at 20:08
  • \$\begingroup\$ Right, so.. don't (re)implement any PRNG; set up your Docker volumes properly. \$\endgroup\$
    – Reinderien
    Commented Jan 18 at 20:11
  • 2
    \$\begingroup\$ @Reinderien I find this a bit dogmatic, to state one should never re-implement one's own PRGP. The alternative is to be stuck with TBs of mock data. I mean, it's not like I'm so deluded that I implement my own "crypto-safe" PRNG here (like Telegram, lol). \$\endgroup\$
    – Amaterasu
    Commented Jan 19 at 9:45
  • \$\begingroup\$ Anyway, I leave that question open for its own sake (as an exercise) even if any real deployment may not be a good idea. \$\endgroup\$
    – Amaterasu
    Commented Jan 19 at 17:30

2 Answers 2

3
\$\begingroup\$

SimpleRandom is an incredibly generic name. I'd call the thing after which it is designed; MwcRandomGenerator would be more appropriate. One problem with this generator is that it seems to be first defined in a USENET post, which is possibly you may not want to use as a reference. This one has some more code as well as test vectors. Note that it simply uses w and z as variable names; I'd keep to original variable names rather than deviating from them.

One problem that I have with the algorithm is that the seed cannot be just any value but that it needs to be within 0 and 2^32 - 2. That makes it more appropriate as some kind of implementation detail than for generic usage (creating a test set of values would be a valid use case of course). I'd rather do a mod 2^32 - 3 than simply trowing an error, creating a very dangerous runtime failure mode in a class called SimpleRandom; at the very least it should be clearly documented.

The error displayed on the seed must be between 0 and 2^32 - 3 should clearly indicate if the values are incusive or exclusive. Now it is inclusive for 0 and exclusive for 2^32. This is common method for ranges in programming, but for human language it is inconclusive. I don't think this error is for user consumption so indicating that it should be in the range [0, 2^32 - 3) would probably be better.

Obviously testing the RNG should consist of much more than simply printing out a few values. It is important to test the the bounds given in the algorithm, e.g.the ones for the seed talked about before. Furthermore, I would at least test against official test vectors or otherwise a known-good implementation. Just comparing some values by hand is not sufficient.


Disclaimer: I did not do an in depth review of the language specific features nor to test if the random implementation is correct.

\$\endgroup\$
3
  • \$\begingroup\$ BTW Thanks that was an interesting travel into history. I also found out that Google will stop archiving USENET, which worries me somewhat. \$\endgroup\$ Commented Jan 20 at 13:46
  • \$\begingroup\$ “One problem with this generator is that it seems to be first defined in a USENET post, which is possibly you may not want to use as a reference.” Just because it was first published on USENET doesn’t mean it wasn’t later published in a peer-reviewed journal. In any case, the author is a well known and well respected researcher in pseudo-random number generation. en.m.wikipedia.org/wiki/George_Marsaglia \$\endgroup\$ Commented Jan 20 at 15:36
  • \$\begingroup\$ @CrisLuengo Oh, I wasn't trying to take anything from the algorithm or the author. It's just that if I'd have to review the code I'd have something to say about using an algorithm that doesn't have a standard nor a well accepted paper that describes it. An auditor would have to research it and come to a conclusion about its distribution. There exist many well known algorithms for non-secure PRNG's so it is not like there are no alternatives. \$\endgroup\$ Commented Jan 20 at 16:16
3
\$\begingroup\$

masking

In next we mask more or less at random, using binary & AND or using % modulo. Prefer to be consistent, performing the same operation in the same way.

Consider naming that magic number, and ditching those four modulos:

mask16 = 0xFFFF
mask32 = 0xFFFF_FFFF

Prefer hex over a decimal constant like 65_535.

bias

The MWC approach produces approximately 32 bits of randomness (ignoring that it avoids getting stuck in an "all zeros" loop). We harvest that randomness with a randrange(1000, 2000) call, for a range of 2000 - 1000 == 1000. It is worth noting that 1000 is not a power of two, so the % modulo introduces a little bias, making some numbers more popular.

A typical fix would be to identify a relevant mask, 0x3FF, extract those bits, and then do rejection sampling. That is, if the masked quantity is a thousand or more, call next() again to re-roll, hopefully obtaining a smaller number.

There's no docstring on randrange(). If there was one, it might note that zero is a possible result, unlike the situation with next().

OBOB

  this.choices = function (arr, k) {
    if (!Number.isInteger(k) || k < 0) throw new Error('k must be a positive integer')

The diagnostic meant to say "... a non-negative integer".

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I was so focused on the algorithm that I was missing the bias :P \$\endgroup\$ Commented Jan 20 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.