Better random function in JavaScript

Question

I'm currently making a Conway's Game of Life reproduction in JavaScript and I've noticed that the function Math.random() is always returning a certain pattern. Here's a sample of a randomized result in a 100x100 grid:

Does anyone knows how to get better randomized numbers?

ApplyRandom: function() {

    var $this = Evolution;

    var total = $this.Settings.grid_x * $this.Settings.grid_y;
    var range = parseInt(total * ($this.Settings.randomPercentage / 100));

    for(var i = 0; i < total; i++) {
      $this.Infos.grid[i] = false;
    }

    for(var i = 0; i < range; i++) {
      var random = Math.floor((Math.random() * total) + 1);
      $this.Infos.grid[random] = true;
    }

    $this.PrintGrid();
  },

[UPDATE]

I've created a jsFiddle here: http://jsfiddle.net/5Xrs7/1/

[UPDATE]

It seems that Math.random() was OK after all (thanks raina77ow). Sorry folks! :(. If you are interested by the result, here's an updated version of the game: http://jsfiddle.net/sAKFQ/

(But I think there's some bugs left...)

Answer 1

A better solution is probably not to randomly pick points and paint them black, but to go through each and every point, decide what the odds are that it should be filled, and then fill accordingly. (That is, if you want it on average %20 percent chance of it being filled, generate your random number r and fill when r < 0.2 I've seen a Life simulator in WebGL and that's kinda what it does to initialize...IIRC.

Edit: Here's another reason to consider alternate methods of painting. While randomly selecting pixels might end up in less work and less invocation of your random number generator, which might be a good thing, depending upon what you want. As it is, you seem to have selected a way that, at most some percentage of your pixels will be filled. IF you had kept track of the pixels being filled, and chose to fill another pixel if one was already filled, essentially all your doing is shuffling an exact percentage of black pixels among your white pixels. Do it my way, and the percentage of pixels selected will follow a binomial distribution. Sometimes the percentage filled will be a little more, sometimes a little less. The set of all shufflings is a strict subset of the possibilities generated this kind of picking (which, also strictly speaking, contains all possibilities for painting the board, just with astronomically low odds of getting most of them). Simply put, randomly choosing for every pixel would allow more variance.

Then again, I could modify the shuffle algorithm to pick a percentage of pixels based upon numbers generated from a binomial probability distribution function with a defined expected/mean value instead of the expected/mean value itself, and I honestly don't know that it'd be any different--at least theoretically--than running the odds for every pixel with the expected/mean value itself. There's a lot that could be done.

Answer 2

This line in your code...

var position = (y * 10) + x;

... is what's causing this 'non-randomness'. It really should be...

var position = (y * $this.Settings.grid_x) + x;

I suppose 10 was the original size of this grid, that's why it's here. But that's clearly wrong: you should choose your position based on the current size of the grid.

---

As a sidenote, no offence, but I still consider the algorithm given in @JayC answer to be superior to yours. And it's quite easy to implement, just change two loops in ApplyRandom function to a single one:

var bias = $this.Settings.randomPercentage / 100;
for (var i = 0; i < total; i++) {
  $this.Infos.grid[i] = Math.random() < bias;
}

With this change, you will no longer suffer from the side effect of reusing the same numbers in var random = Math.floor((Math.random() * total) + 1); line, which lowered the actual cell fillrate in your original code.

Answer 3

Math.random is a pseudo random method, that's why you're getting those results. A by pass i often use is to catch the mouse cursor position in order to add some salt to the Math.random results :

Math.random=(function(rand) {
  var salt=0;
  document.addEventListener('mousemove',function(event) {
    salt=event.pageX*event.pageY;
    });
return function() { return (rand()+(1/(1+salt)))%1; };
})(Math.random);

It's not completly random, but a bit more ;)

Answer 4

The implementation of Math.random probably is based on a linear congruential generator, one weakness of which is that a random number depends on the earlier value, producing predictable patterns like this, depending on the choice of the constants in the algorithm. A famous example of the effect of poor choice of constants can be seen in RANDU.

The Mersenne Twister random number generator does not have this weakness. You can find an implementation of MT in JavaScript for example here: https://gist.github.com/banksean/300494

---

Update: Seeing your code, you have a problem in the code that renders the grid. This line:

var position = (y * 10) + x;

Should be:

var position = (y * grid_x) + x;

With this fix there is no discernible pattern.

Answer 5

You can try

• JavaScript Crypto Library (BSD license). It is supposed to have a good random number generator. See here an example of usage.
• Stanford JavaScript Crypto Library (BSD or GPL license). See documentation for random numbers.

For a discussion of strength of Math.random(), see this question.

Answer 6

You can using the part of sha256 hash from timestamp including nanoseconds:

console.log(window.performance.now()); //return nanoseconds inside

This can be encoded as string, then you can get hash, using this: http://geraintluff.github.io/sha256/

salt = parseInt(sha256(previous_salt_string).substring(0, 12), 16);
//48 bits number < 2^53-1

then, using function from @nfroidure, write gen_salt function before, use sha256 hash there, and write gen_salt call to eventListener. You can use sha256(previous_salt) + mouse coordinate, as string to get randomized hash.