Generate random numbers from various distributions.
d3 / d3-random Goto Github PK
View Code? Open in Web Editor NEWGenerate random numbers from various distributions.
Home Page: https://d3js.org/d3-random
License: ISC License
Generate random numbers from various distributions.
Home Page: https://d3js.org/d3-random
License: ISC License
Generate random numbers from various distributions.
This module seems incomplete without a seeded RNG, we could use this very neat linear congruential generator
https://observablehq.com/@fil/linear-congruential-generator
It would be useful for tests, and anecdotically for d3-force/jiggle
It might be nice to add a Pareto distribution generator.
Here is an implementation, using math from http://www.cse.wustl.edu/~jain/books/ftp/ch5f_slides.pdf, page 32:
function pareto(alpha){
return function(){
return 1 / Math.pow(Math.random(), 1 / alpha);
};
}
Also, here's an example that uses this implementation. You can see visually that the distribution looks correct, but I could not wrap my head around how to make a proper test for this. Unfortunately I cannot offer a complete implementation with tests, but I just thought I'd put this idea/feature request up here.
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 :)
The manufacturing and reliability fields use the Weibull distribution extensively. It is also a generalized distribution for a few others, Rayleigh and others. So, it is a good bang for the buck.
I'm not confident I can create the code in this format without help, as I can't run test and debug locally (yet!). But, I think I can help another contributor if there is desire.
I took a shot in creating prototype code following existing examples, and have ideas about the unit tests but not coded them.
Let me know if/how I can help.
Troy
Note: Created notebook and coded formula: https://observablehq.com/@troymagennis/weibull-distribution
import defaultSource from "./defaultSource.js";
export default (function sourceRandomWeibull(source) {
function randomWeibull(alpha, lambda) {
// reference: https://en.wikipedia.org/wiki/Weibull_distribution
// some guarding against null
alpha = alpha == null ? 0 : +alpha;
lambda = lambda == null ? 0 : +lambda;
return function() {
return lambda * Math.pow(-Math.log(1.0 - source()), (1.0/alpha));
};
}
randomWeibull.source = sourceRandomWeibull;
return randomWeibull;
})(defaultSource);
/* test cases
Median should equal : lambda * math.Pow(math.Log(2.0), 1.0 / alpha);
Shape parameter of 1 should equal the exponential distribution values for the same scale parameter
*/`
```
So the new pretest script still has some issues, it fails on windows with the error log attached below. I did some digging around and it seems that the json2module
module tries to read and write from and to dev/stdin and dev/stdout respectively. The problem with this is that windows has no analogue for these device files. Related: http://superuser.com/questions/241272/windows-how-to-redirect-file-parameter-to-stdout-windows-equivalent-of-dev-s
> [email protected] pretest ~\d3-random
> rm -rf build && mkdir build && json2module package.json > build/package.js && rollup -f umd -n d3_random -o build/d3-random.js -- index.js
~\d3-random\node_modules\json2module\bin\json2module:21
if (error) throw error;
^
Error: ENOENT: no such file or directory, open 'C:\dev\stdout'
at Error (native)
npm ERR! Windows_NT 6.3.9600
npm ERR! argv "C:\\Program Files\\nodejs\\node.exe" "C:\\Program Files\\nodejs\\node_modules\\npm\\bin\\npm-cli.js" "run" "test"
npm ERR! node v5.0.0
npm ERR! npm v3.3.6
npm ERR! code ELIFECYCLE
npm ERR! [email protected] pretest: `rm -rf build && mkdir build && json2module package.json > build/package.js && rollup -f umd -n d3_random -o build/d3-random.js -- index.js`
npm ERR! Exit status 1
npm ERR!
npm ERR! Failed at the [email protected] pretest script 'rm -rf build && mkdir build && json2module package.json > build/package.js && rollup -f umd -n d3_random -o build/d3-random.js -- index.js'.
npm ERR! This is most likely a problem with the d3-random package,
npm ERR! not with npm itself.
npm ERR! Tell the author that this fails on your system:
npm ERR! rm -rf build && mkdir build && json2module package.json > build/package.js && rollup -f umd -n d3_random -o build/d3-random.js -- index.js
npm ERR! You can get their info via:
npm ERR! npm owner ls d3-random
npm ERR! There is likely additional logging output above.
npm ERR! Please include the following file with any support request:
npm ERR! C:\Users\Pepe\dropbox\workspace\d3-random\npm-debug.log
npm ERR! Windows_NT 6.3.9600
npm ERR! argv "C:\\Program Files\\nodejs\\node.exe" "C:\\Program Files\\nodejs\\node_modules\\npm\\bin\\npm-cli.js" "install"
npm ERR! node v5.0.0
npm ERR! npm v3.3.6
npm ERR! code ELIFECYCLE
npm ERR! [email protected] prepublish: `npm run test && uglifyjs build/d3-random.js -c -m -o build/d3-random.min.js && rm -f build/d3-random.zip`
npm ERR! Exit status 1
npm ERR!
npm ERR! Failed at the [email protected] prepublish script 'npm run test && uglifyjs build/d3-random.js -c -m -o build/d3-random.min.js && rm -f build/d3-random.zip'.
npm ERR! This is most likely a problem with the d3-random package,
npm ERR! not with npm itself.
npm ERR! Tell the author that this fails on your system:
npm ERR! npm run test && uglifyjs build/d3-random.js -c -m -o build/d3-random.min.js && rm -f build/d3-random.zip
npm ERR! You can get their info via:
npm ERR! npm owner ls d3-random
npm ERR! There is likely additional logging output above.
npm ERR! Please include the following file with any support request:
npm ERR! ~\d3-random\npm-debug.log
We currently discard one of those values, but maybe we should save it for the next time the random number generator is called?
When placing a Go stone in each quadrant, we get a pair of intervals:
0 <= coordinate < 9.5
9.5 <= coordinate < 19
Currently, randomInt(0, 9.5)
is equivalent to randomInt(0, 9)
, making it unsuitable.
Now, it's not difficult to do it with randomUniform()
but I wondered why the parameters min
and max
are floored individually instead of only the result of calculation.
Since Math.random could potentially return the same value twice and it is not cryptographically secure causing the insecure randomness when we scan the code in the fortify tool.
Please confirm if there is any future plan to remove Math.random and use cryptographically secure code for getting random values.
just by using crypto API
const myArray = new Uint32Array(10);
crypto.getRandomValues(myArray);
lcg: https://github.com/d3/d3-random/blob/main/src/lcg.js#L6
deafultSource.js: https://github.com/d3/d3-random/blob/main/src/defaultSource.js#L1
Below APIs are dependent on the defaultsource which gives Math.random values
d3.uniform
d3.int
d3.normal
d3.logNormal
d3.irwinHall
d3.bates
d3.exponential
d3.pareto
d3.bernoulli
d3.geometric
d3.gamma
d3.beta
d3.binomial
d3.weibull
d3.cauchy
d3.logistic
d3.poisson
Hi,
I was wondering what exactly the intended direction for this D3 module is? With which I mean, is it supposed to be used to model/simulate all kinds of statistical processes and events? if so shouldn't it also include more frequently used distributions, such as Bernoulli, Bionomial, Geometric, Pareto, to name a few?
I would gladly implement a few of these distributions and create a pull request, however I thought I'd ask first, to make sure I wouldn't be wasting my time.
Cheers!
I'm wondering if you'd be interested in supporting cryptographically-secure or seeded random generators?
If so, I'd be willing to work on it, but there are multiple approaches, so I'd want your feedback before doing any work.
The idea would be to replace anywhere in the current code base that uses Math.random() with a custom random function. If you don't pass a custom random function, then one would be chosen for you using an algorithm (to be decided by you).
For instance, the node-uuid
lib uses the following:
In node, it tries to use require('crypto').randomBytes (link), in the browser it tries to WebCrypto (link, link), then falls back to Math.random() in both scenarios.
I'm not sure how important cryptographically secure generators are in this lib, but it would be cool to have the option, along with seeded generators (that way you could create random distributions that always return the same values- for testing, etc).
Right now, you can use d3-random
with a seeded generator, but you have to monkey patch Math.random(), i.e.:
var d3 = require('d3-random');
var seeded = require('random-seed').create('some custom seed');
Math.random = seeded.random;
// Return a number greater than or equal to 0
// and less than 6, based on the 'some custom seed' seed:
d3.uniform(6)();
It would be nice to have a way to use a custom PRNG without monkey patching Math.random(), but that would involve changing or re-thinking the API a bit (I'm guessing). I'm also not sure how to convert crypto.randomBytes into a good uniform 0..1, so that would require some research (for me at least- I'm sure it's already been solved by others).
As far as the API changes, I have a few ideas, but haven't spent much time thinking about it. Some quick thoughts:
random
as either the first or last parameter of all functions. If typeof random !== 'function'
then Math.random
would be used (or a more complex algorithm similar to node-uuid- based on how performant you want this lib to be, and how complex of a "choose default" you want to maintain).uniform.random = Math.random
by default; Users could then: var d3 = require('d3-random');d3.uniform.random = myRandomFunction;d3.uniform(6)();
I have more ideas, but this is getting to be a long post, so I'll wait for feedback :)
More Math.random() / crypto / prng links:
We should have a randomInt method that returns an integer greater than or equal to min and less than max.
function randomInt(min, max) {
if (arguments.length < 2) max = min, min = 0;
min = Math.floor(min);
max = Math.floor(max) - min;
return () => Math.floor(min + Math.random() * max);
}
Adding frac(n) * uniform in https://github.com/d3/d3-random/blob/master/src/irwinHall.js would allow to generalize bates and Irwin-Hall to non-integers n. https://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution#Extensions_to_the_Irwin%E2%80%93Hall_distribution
Would there be a use case for a Perlin noise function in this module? I can see two functions: perlin2d and perlin3d as useful in creating random but continuous distributions. One use case would be to return a single noise value. Other use cases I can think of are to return an array of noise depending on the given interval. May also be useful in using with d3.contour for procedural generation of contours.
If you guys think this may be useful, I have been working something and could send a PR.
The poisson distribution is very commonly used and would be useful to include:
When cloning the repo and doing npm install
, the pretest script fails on windows machines.
npm-debug.log: https://www.dropbox.com/s/5fxh5u7t0omeq7h/npm-debug.log?dl=0
Additional information:
randomLatitude = r => acos(2*r - 1) would be quite useful, probably with a range of [-90,90] by default.
I had also thought of randomGeoPoint = (r1, r2) => [ -180 + 360 * r1, randomLatitude(r2) ] ; but it feels a bit awkward as it would not be a 1d distribution — maybe it should belong to d3-geo instead.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.