You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Would there be any interest in xorshift32, xorshift64 and xorwow32? #39
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.
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)
constu=newUint32Array(1);constf=newFloat32Array(u.buffer);letx=(Math.random()*0x100000000)|0;returnfunctionxorShiftF32(){// closures never inline captured variables,// hence this local variable to fix thatlet_x=x;_x^=_x<<13;_x^=_x>>17;_x^=_x<<5;u[0]=0b111111100000000000000000000000|(_x&0x7fffff);x=_x;returnf[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 :)
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.)
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:
constn=1e7;constA=newArray(n).fill(0);lettime=+newDate();for(leti=0;i<n;i++)A[i]=xorShiftF32Mul();time=(+newDate()-time)/1000;returnmd` ${(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)
Activity
Fil commentedon Nov 9, 2020
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 commentedon Nov 12, 2020
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 thanMath.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:
Chrome
Firefox
(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 commentedon May 12, 2021
have you tried this using wasm to see if it's faster still?
JobLeonard commentedon May 12, 2021
There's one notebook where I tried - it's slower. The call overhead is bigger than whatever perf benefits the WASM code might have