4
\$\begingroup\$

I'm implementing some of lodash JavaScript library functions like (min, max, sum, ceil, floor, random) and unit testing them for practice, however, testing the random function was tricky.

The random number generator function :-

let random = (min, max) => {
    if (min === undefined && max === undefined) {
        return Math.random();
    }
    // if one parameter is passed, assign it to lonelyPar
    let lonelyPar = min === undefined? max : max === undefined? min : undefined;
    if (lonelyPar) {
        min = 0, max = lonelyPar;
    }
    if (min > max) {
        let temp = min;
        min = max;
        max = temp;
    }
    return this.floor(Math.random() * (max - min + 1) + min);
}

It behaves like this:-

  • If it's called with no parameters, it returns the value of Math.random() (random number between 0 and 1)
  • If it's called with one parameter, it returns a random number between 0 and it inclusive.
  • If it's called with two parameters, it returns a random number between them inclusive.

The unit testing using Mocha and Chai Assertion Library :-

describe('random function', () => {
    let getUniqRandGenNums = numOfPars => {
        let randomsNumbers = [];
        let params = [[], [5], [1, 10]][numOfPars];
        for (var i = 0; i < 10000; i++) {
            randomsNumbers.push(random(...params));
        }
        randomsNumbers = [...new Set(randomsNumbers)];
        let minRandom = min(randomsNumbers); // I implemented min
        let maxRandom = max(randomsNumbers); // I implemented max
        return {
            randomsNumbers,
            minRandom,
            maxRandom
        }
    }
    describe('no patameters passed', () => {
        let result = getUniqRandGenNums(0);
        let minRandom = result.minRandom;
        let maxRandom = result.maxRandom;
        let randomsNumbers = result.randomsNumbers;
        it('should generate different numbers', () => {
            expect(randomsNumbers.length).to.be.above(1);
        });
        it('should not generate a number below the lower bound', () => {
            expect(minRandom).to.be.within(0, 1);
        });
        it('should not generate a number above the upper bound', () => {
            expect(maxRandom).to.be.within(0, 1);
        });
    });
    describe('one patameter passed', () => {
        let result = getUniqRandGenNums(1);
        let minRandom = result.minRandom;
        let maxRandom = result.maxRandom;
        let randomsNumbers = result.randomsNumbers;
        it('should generate different numbers', () => {
            expect(randomsNumbers.length).to.be.above(1);
        });
        it('should not generate a number below the lower bound', () => {
            expect(minRandom).to.be.within(0, 5);
        });
        it('should not generate a number above the upper bound', () => {
            expect(maxRandom).to.be.within(0, 5);
        });
    });
    describe('two patameters passed', () => {
        let result = getUniqRandGenNums(2);
        let minRandom = result.minRandom;
        let maxRandom = result.maxRandom;
        let randomsNumbers = result.randomsNumbers;
        it('should generate different numbers', () => {
            expect(randomsNumbers.length).to.be.above(1);
        });
        it('should not generate a number below the lower bound', () => {
            expect(minRandom).to.be.within(1, 10);
        });
        it('should not generate a number above the upper bound', () => {
            expect(maxRandom).to.be.within(1, 10);
        });
    });
});

I'm testing 2 things :-

  • It doesn't generate the same number every time
  • It doesn't generate a number out of the given range

I do this by generating 10,000 random numbers and storing them in an array, remove the duplication, get the minimum and maximum numbers.

test case 1: I test that the array length is greater than 1

test case 2: the minimum and maximum numbers are within the range

I'm using a small range, 1 to 10 in case it's called with two parameters, so it has most likely generated all the numbers in that range after 10,000 calls, which makes me sure that these are the lowest min number and highest max number it can generate within that range.

What do you think about my approach of testing it and how would you test it?

Link to the repo of the project for a better view.

Note: Execuse my bad English, I'm not a native speaker.

\$\endgroup\$
3
\$\begingroup\$

Since you are swapping the min and max if the user provides them in wrong order; instead of raising an error, you can use the || operator to assign values:

temp_min = Math.min(min || 0, max || 0),
temp_max = Math.max(min || 0, max || 0)

As for tests, the ideal RNG test should be that it is generating the values in the interval \$ (min, max) \$ with equal probabilities. For that, you can keep a count of each value in the \$ 10000 \$ iterations, and check that the counts are nearly equal.

\$\endgroup\$
  • \$\begingroup\$ How would an error be raised by that? \$\endgroup\$ – Mark Adel Jan 10 '18 at 17:07
  • \$\begingroup\$ @MarkAdel I've seen that behaviour in other languages, where if min > max, the program raises an error. \$\endgroup\$ – hjpotter92 Jan 10 '18 at 17:13
  • \$\begingroup\$ I'm already doing a swap if min > max \$\endgroup\$ – Mark Adel Jan 10 '18 at 17:39
  • \$\begingroup\$ @MarkAdel I saw that. Which is why I said that since you're swapping, you can use ||. Perhaps my phrasing wasn't good. \$\endgroup\$ – hjpotter92 Jan 10 '18 at 17:47
  • \$\begingroup\$ Aha got it, that's also handled, I checked in a previous condition that non of them is undefined, also passing only one parameter is handled, but that's a good point, thanks. \$\endgroup\$ – Mark Adel Jan 10 '18 at 17:59
2
\$\begingroup\$

Random values.

There is no real way to test random values. You can only say how random it is and what type of distribution it gives. Eg the string "aaaaaaa" could be generated by a perfect random generator, that is the nature of random. (as the infinite monkeys randomly typing can produce all the written works of man, and if possible a perfect random number generator)

Also take it as a given that scaling a random value does not affect its randomness. Just as you don't have to test code that adds numbers (assert(1 + 1, 2) needless testing) the same applies to a scaled random value (within floating point limits that is). For most applications Math.random() * value is still as random as Math.random()

Testing random

First of

It doesn't generate the same number every time

That is a given for Math.random() and you don't need to test it

It doesn't generate a number out of the given range

You don't need to test a large set of values. You only need test the expression and that is so simple I would not consider it something to test apart from ensuring there are not typos.

So just substitute Math.random so you can control what it returns then test min and close to 1

Math.random = ()=>0;
// test for min
Math.random = ()=> 1 - Number.EPSILON;
// test for max

Mean test

The simplest test is to look at the mean. The mean over time should get closer to 0.5.

const tests = 100000
var count = 0;
var sum = 0;
var mean = 0;
function testRandom(){
    for(var i = 0; i < tests; i++){
        sum += Math.random(); 
    }
    count += tests;
    mean = sum / count;
    result.textContent = mean;
}

(function doTest(){
    testRandom()
    if(count < 1000000000){
        setTimeout(doTest,10);
    }
})();
Random mean<span id="result"></span>

Distrubution test

But this does not tell you about the distribution of the values. There are many types of distributions all of which are random. For the Math.random value you want a flat distribution.

One way is to use buckets to collect random values and then test the standard deviation of the bucket levels. By comparing the standard deviation against the max bucket level you get a randomness that is a measure of how evenly the distribution is. This value should approch 1 over time.

const ctx = canvas.getContext("2d");
const tests = 100000
const buckets = new Float64Array(canvas.width);
var count = 0;
var sum = 0;
var mean = 0;
function testRandom(){
    const w = canvas.width;
    for(var i = 0; i < tests; i++){
        buckets[Math.random() * w | 0] += 1; 
    }
    count += tests;
}

(function doTest(){
    testRandom();
    if(count < 1000000000){
        setTimeout(doTest,10);
    }
})();

function updateCanvas(){
    ctx.clearRect(0,0,ctx.canvas.width,ctx.canvas.height);
    const w = canvas.width;
    var max = 0;
    var min = Infinity;
    var sum = 0;
    for(var i = 0; i < w; i++){
        max = Math.max(buckets[i],max);
        min = Math.min(buckets[i],min);
        sum += buckets[i];
    }
    mean = sum / w;
    var variance = 0;
    for(var i = 0; i < w; i++){
        variance = Math.pow(mean - buckets[i], 2);
    }
    variance /= w;
    

    randomness.textContent =1-Math.sqrt(variance)/ max;
    for(var i = 0; i < w; i++){
        const level =((buckets[i] - min) / (max-min)) * ctx.canvas.height |  0;
        ctx.fillRect(i,ctx.canvas.height - level,1, level);
    }
    
    requestAnimationFrame(updateCanvas);

}
requestAnimationFrame(updateCanvas);
<canvas id="canvas" width = 500></canvas><br>
Randomness <span id="randomness"></span><br>

The next example shows how the tests handle other types of random showing how mean is unaffected while randomness (flatness of distribution) approaches values below 1. All gaussian like approximations.

const ctx = canvas.getContext("2d");
const tests = 1000
const buckets = new Float64Array(canvas.width);
var count = 0;
var sum = 0;
var mean = 0;
const randG  = (min = 1, max = min + (min = 0), p = 2) => (max + min) / 2 + (Math.pow(Math.random(), p) * (max - min) * 0.5) * (Math.random() < 0.5 ? 1 : -1);
const randB = (min = 1, max = min + (min = 0), p = 2) => {
    p = Math.max(1,(p | 0));
    var r = 0;
    var i = 0;
    while(i++ < p){
        r += Math.random();
    }
    return r / p;
}

var randomFunc = randG;
var randoms = [randG,()=>randG(0,1,1.1),randB,()=>randB(0,1,4)]
var names = ["Simple gaussian","Simple gaussian wide","Bell simple","Bell smooth"];
var currentRandom = 0;
canvas.addEventListener("click",()=>{
    currentRandom += 1;
    randomFunc = randoms[currentRandom % randoms.length];
    sum = 0;
    count = 0;
    buckets.fill(0);
    namesel.textContent = names[currentRandom % randoms.length];
})

function testRandom(){
    const w = canvas.width;
    for(var i = 0; i < tests; i++){
        const rand = randomFunc();
        sum += rand;
        buckets[rand * w | 0] += 1; 
    }
    count += tests;
    result.textContent = sum / count;
}

(function doTest(){
    testRandom();
    if(count < 1000000000){
        setTimeout(doTest,10);
    }
})();

function updateCanvas(){
    ctx.clearRect(0,0,ctx.canvas.width,ctx.canvas.height);
    const w = canvas.width;
    var max = 0;
    var min = Infinity;
    var sum = 0;
    for(var i = 0; i < w; i++){
        max = Math.max(buckets[i],max);
        min = Math.min(buckets[i],min);
        sum += buckets[i];
    }
    mean = sum / w;
    var variance = 0;
    for(var i = 0; i < w; i++){
        variance = Math.pow(mean - buckets[i], 2);
    }
    variance /= w;
    

    randomness.textContent =1-Math.sqrt(variance)/ max;
    for(var i = 0; i < w; i++){
        const level =((buckets[i] - min) / (max-min)) * ctx.canvas.height |  0;
        ctx.fillRect(i,ctx.canvas.height - level,1, level);
    }
    
    requestAnimationFrame(updateCanvas);

}
requestAnimationFrame(updateCanvas);
<h3 id="namesel">Click graph to change random types</h3>
<canvas id="canvas" width = 500 height = 100></canvas><br>
Mean <span id="result"></span><br>
Randomness <span id="randomness"></span><br>
Randomness asymptotically approaches a value less than 1 yet the mean still approaches 0.5.

There are many other tests. But it is important to note that none of them are perfect and all can be fooled or give erroneous results. The only way to improve the results is to increase the sample count. The above functions test 100s of millions of samples, but there is a flaw in Math.random its ultimately based on binay , that will start to show up if you have a very very long time to run the tests.

It's not how random, it's random for what.

It's about what you want from the random values. Javascripts random is not good enough for high security encryption or hashing, but random enough for games of chance, though generally casinos will use their own random generators.

For games, image processing, its is more than enough. And for things like playlist shuffle it's too random.

Javascript and function signatures.

I have never found a good reason to write an inclusive random function. and I do not understand why some many people do? So all the example will not include inclusive calculations. I leave it to you to add the + 1 if you need it.

Default parameters

You can use javascripts default parameters to do most of the parameter logic for you.

I think it better to have separate double and integer functions

const rand  = (min = 1, max = min + (min = 0)) => Math.random() * (max - min) + min;
const randI  = (min = 2, max = min + (min = 0)) => Math.random() * (max - min) + min | 0;

The signature behaviours.

  • If no arguments them return result of 0-1 for double or 0 or 1 for integer
  • If one argument then random values from 0 to argument non inclusive
  • If two argument then random values from arg1 to arg2 non inclusive

The trick is the second default parameter needs to set the first argument to 0 and assign the second argument to the first. The only way to do that is to use an expression max = min + (min = 0) . The order lets you effectively swap the variables without the need of a interim value.

Another example is a gaussian random where the random values are distributed around the mean. A third parameter is needed to define the distribution curve

const randG  = (min = 1, max = min + (min = 0), p = 2) => 
    (max + min) / 2 + 
    (Math.pow(Math.random(), p) * (max - min) * 0.5) * 
    (Math.random() < 0.5 ? 1 : -1);

The function has 4 signatures all non inclusive

randG(); // random gaussian  from 0-1 center at 0.5 distribution cof 2 
randG(4); // random gaussian from 0-4 center at 2  distribution cof 2
randG(2,4); // random gaussian from 2-4 center at 3  distribution cof 2
randG(2,4,5); // random gaussian from 2-4 center at 3  distribution cof 5

When picking a card from a deck you use a flat distribution as Math.random does. If assigning the random size of an apple you use a gaussian distribution.

And just for interest

A few other variations

randItem returns a random item from an array, randPick removes a random item from an array, and randPut puts a item at a random position in an array. And a seeded random (Not as good as Math.random but more than enough for most applications) Seeding allows you to repeat a random sequence which can be extremely handy. Same as all rand functions just add a S after rand and to seed call randSeed(Date.now()) to make unpredictable or randSeed(value)

const randItem = (array) => array[(Math.random() * array.length) | 0];
const randPick = (array) => array.splice((Math.random() * array.length) | 0,1)[0];
const randPut = (array,item) => array.splice((Math.random() * (array.length+1)) | 0,0,item);

const sRandom = (() => {
    var seed = 1;
    return { 
        max : 2576436549074795, 
        reseed (s) { seed = s }, 
        rand ()  { 
            return seed = ((8765432352450986 * seed) + 8507698654323524) % this.max 
        }
    }
})();
const randSeed = (seed) => sRandom .reseed(seed|0);
const randSI = (min, max = min + (min = 0)) => (sRandom .random() % (max - min)) + min;
const randS  = (min = 1, max = min + (min = 0)) => (sRandom .random() / sRandom .max) * (max - min) + min;
const randSItem = (array) => array[sRandom .random() % array.length];
const randSPick = (array) => array.splice(sRandom .random() % array.length,1)[0];
const randSPut = (array,item) => array.splice(sRandom .random() % (array.length+1),0,item)[0];

\$\endgroup\$
  • 1
    \$\begingroup\$ The OP has presented particular properties of an rng they wish to test. Instead of focusing on how to perform those tests, your answer is telling them what tests they should do. "That is a given for Math.random() and you don't need to test it" Not testing things because they obviously should work is really bad practice. "You only need test the expression and that is so simple I would not consider it something to test apart from ensuring there are not typos." It's really not clear what you're trying to say here. \$\endgroup\$ – Acccumulation Jan 10 '18 at 22:53
  • \$\begingroup\$ @Acccumulation you can not test random, you can only increase the probability that it is working, so I advised him to test by replacing the random function so he can test the expression this.floor(Math.random() * (max - min + 1) + min). And no it is far from bad practice to assume that native JS is working. Or are you saying we should test every native function we use??? How do you test if you can not trust the native JS. What about operators and statements, is it bad practice to assume they work. \$\endgroup\$ – Blindman67 Jan 10 '18 at 23:56
0
\$\begingroup\$

Figuring out how to test if the RNG is statistically sound is tricky, and you need to have some good idea of what is and is not "too improbable" to consider valid. This question has some useful pointers on how you might test the actual randomness of the generator.

That being said, I think it is also worthwhile to make sure that the expected properties of the generated number are always true. You might use property based testing to assert something about the properties without knowing the specific input or what the exact result should be..

Suppose we were testing integer addition. The properties of integer addition are:

  1. Identity: $$x + 0 = x$$
  2. Associativity: $$(x + y) + z = x + (y + z)$$
  3. Commutativity: $$x + y = y + x$$

Then, to test this with property-based testing, we'd do something like this:

function identity(x)
{
    let result = add(x, 0)
    return result === x;
}

function test_property(property_callback, num_params, param_generators)
{
    var num_failed = 0;
    for (var i = 0; i < big_number; ++i)
    {
        var params = [];
        for (var param = 0; param < num_params; ++param)
        {
            params[param] = param_generators[param]();
        }

        if (!property_callback.apply(null, params))
        {
            save_failed_input(input, property_callback);
            ++num_failed;
        }
    }
    return num_failed;
}

test_property(identity, 1, [integer_generator_function]);

They can get a lot more sophisticated than that, but the gist is that you aren't defining the inputs and outputs explicitly (which is hard to do for testing an RNG) but rather saying that for inputs of a certain class, we expect these properties to always be true. If they aren't true, it remembers those values and reports them to you, and if the tester is sophisticated enough it'll remember them and always test them in the future.

This doesn't handle whether or not the RNG is actually behaving "randomly", but whether or not it'll always satisfy your invariants. That should be enough for you to feel confident that code that relies on those invariants will function, but not necessarily that they will be as random as you would hope.


JSVerify

JSVerify is a tool for JavaScript to do this; there might be others, but this is the first one that Google showed me. Here is how we might use it with Mocha to test the following properties of your function:

  • If no parameters, then the value should be from $$[0,1)$$
  • If one parameter greater than 0, then the value should be from $$[0,x]$$
  • If one parameter less than 0, then the value should be from $$[x,0]$$

As an aside, I didn't see it defined what should happen if random(0) happens; it looks like the code will effectively return Math.Random() but you haven't formally defined it.

describe("random number", () => {
    jsc.property("non-negative", "", () => random() >= 0);
    jsc.property("less than one", "", () => random() < 1);
});

describe("random number 0 to n", () => {
    jsc.property("non-negative", "integer(1, integer)", (integer) => random(integer) >= 0);
    jsc.property("less than or equal to n", "integer(1, integer)", (integer) => random(integer) <= integer);
});

describe("random number -n to 0", () => {
    jsc.property("less than or equal to 0", "integer(integer, -1)", (integer) => random(integer) <= 0);
    jsc.property("greater than or equal to n", "integer(integer, -1)", (integer) => random(integer) >= integer);
});

// etc...

Disclaimer, I've never actually used JSVerify so I might not have done that entirely right.

\$\endgroup\$
-1
\$\begingroup\$

Once you've found the minimum and maximum, you can save a little bit of computation by not finding the number of unique values; the number of unique values is greater than one if and only if min < max. Are there no separate "greater than" or "less than" comparators?

The 5 in 'one patameter passed' (note: should be 'one parameter passed') and 1 and 10 in 'two patameter passed' look like magic numbers. You should define constants equal to these numbers, or pass them as parameters.

You have a lot of repetition; you should consider re-writing it so aren't doing the same thing in different blocks.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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