Would there be any interest in xorshift32, xorshift64 and xorwow32?

[JobLeonard]

I wrote some basic implementations here:

https://observablehq.com/@jobleonard/xorshift (32 bits)

https://observablehq.com/@jobleonard/xorshift64

https://observablehq.com/@jobleonard/xorwow (32 bits)

Also, yesterday I came up with a hack to convert a random integer value to a random float32 or float64 value in the range [0, 1) without multiplication or division.

Try this out in the console:

u = new Uint32Array(2);
f = new Float32Array(u.buffer);
u[0] = 0b0111111100000000000000000000000;
u[1] = 0b1000000000000000000000000000000;
{ u, f };

  // -->  Object {
  //        u:  Uint32Array(2) [1065353216, 1073741824]
  //        f: Float32Array(2) [1, 2]
  //      }

In other words: if we first set a float32 value to 1.0, then cast to it to a uint32, we can bitmask any integer PRNG on the lower 23 bits (the mantissa, basically) to get a uniform random distribution in the range [1.0, 2.0) of Float32 (assuming the chosen integer PRNG has a uniform distribution of integer values).

All we have to do then is subtract one and we should get an approximation of a uniform distributed value in the range [0, 1.0). Ok, not entirely uniform: there will be some rounding errors of course, so I'm sure it'll introduce some bias, but it's going to be close. In JavaScript we can use a typed array to "cast" between integer and float values.

So that leads to a very simple method of using (say) a basic xorshift to create a random number in the range (0,1) (recall that xorshift cannot be zero)

  const u = new Uint32Array(1);
  const f = new Float32Array(u.buffer);
  let x = (Math.random() * 0x100000000) | 0;
  return function xorShiftF32() {
    // closures never inline captured variables,
    // hence this local variable to fix that
    let _x = x;
    _x ^= _x << 13;
    _x ^= _x >> 17;
    _x ^= _x << 5;
    u[0] = 0b111111100000000000000000000000 | (_x & 0x7fffff);
    x = _x;
    return f[0] - 1;
  };

The first xorshift notebook contains both these "shift and subtract" versions and "shift and multiply by epsilon" versions - the multiplication one seems to be faster, but hey, it was worth a shot :)

[Fil]

For me it was important to have one prng, and LCG was ready first. Beyond that, I'm not sure if d3-random should include more than one. At least there needs to be a clear use case or argument for each, since it does not seem worth adding code, documentation and maintenance costs just for the mathematical curiosity.

(I can see what the argument for PCG would be (it's "stronger"), but it would need to be "proven" and I was unable to run the crypto tests.)

[JobLeonard]

Fair arguments in favor of not rocking the boat too much, or adding too many algorithms people won't use. However, in terms of randomness even xorshift32 is better than LCG, IIRC, but I should double-check that.

What might be worth noting is that xorshift32 is a lot faster - it managed beat the built-in Math.random() in Chrome, while still maintaining the 32 bits of randomness. On Firefox xorshift is a bit slower than Math.random(), but LCG is much slower than either (can't speak for other browsers).

Note that the following microbenchmarks are not at all exhaustive, they're basically just doing this:

  const n = 1e7;
  const A = new Array(n).fill(0);

  let time = +new Date();
  for (let i = 0; i < n; i++) A[i] = xorShiftF32Mul();
  time = (+new Date() - time) / 1000;

  return md` ${(n / 1e6 / time).toFixed(
    1
  )} million pseudorandom numbers per second (individual calls to \`xorShiftF32Mul\`)`;

Chrome

Method	pseudorandom numbers per second
Math.random()	23.4 million
LCG	19.0 million
xorShift32Mul	30.7 million

Firefox

Method	pseudorandom numbers per second
Math.random()	270.3 million
LCG	9.2 million
xorShift32Mul	140.8 million

(there's also a version of the algorithm that directly work on an array/typed array instead of doing individual function calls. That one is faster than the native method in either browser, and a lot faster in Chrome's case, but whether or not to add array-based functions is a different discussion)

[hellonearthis]

have you tried this using wasm to see if it's faster still?

[JobLeonard]

There's one notebook where I tried - it's slower. The call overhead is bigger than whatever perf benefits the WASM code might have