7

Screenshot

Edit: This is using Google Chrome 36

I was messing around with html5 canvas, generating points randomly distributed inside a cube and projecting that onto a 2D canvas. Surprisingly, the results don't look very symmetric at all, and I suspect that Javascript's Math.random() is letting me down.

Can anyone tell me why this is happening? Is it possible to make it actually look random, without making it slower?

var ctx = canvas.getContext('2d');

for (var i = 0; i < 10000000; i++) {
    var x = Math.random()*2-1, y = Math.random()*2-1, z = 2+Math.random()*2-1;
    x = (.5 + .5*x/z) * canvas.width;
    y = (.5 + .5*y/z) * canvas.height;
    ctx.fillRect(Math.floor(x), Math.floor(y), 1, 1);
}

http://jsfiddle.net/y10tvj26/ (Takes a while to load)

doeke
  • 462
  • 5
  • 12

2 Answers2

4

Chrome has a documented issue that subsequent calls to Math.random() are correlated. In your algorithm, correlated values will tend to fall on a line on the canvas. An extra call to Math.random() breaks that correlation. I haven't seen reports that other browsers are affected.

Just call Math.random() an extra time on each call, and you'll get what you want.

var ctx = canvas.getContext('2d');

function r() {
    Math.random();
    return Math.random();
}
for (var i=0; i<10000000; i++) {
    var x = r()*2-1, y = r()*2-1, z = 2+r()*2-1;
    x = (.5 + .5*(x/z)) * canvas.width;
    y = (.5 + .5*(y/z)) * canvas.height;
    ctx.fillRect(x, y, 1, 1);
}

Updated on: http://jsfiddle.net/y10tvj26/5/

jimm101
  • 948
  • 1
  • 14
  • 36
  • Why? Please explain how that solves the issue. Also, OP does ask for the *reason* why the pattern emerged in the first place, not [only] how to deal with it. – Bergi Aug 12 '14 at 20:28
  • 1
    I had put a comment regarding that below a different answer, which was otherwise misleading. I edited my response to include the reason and a reference. – jimm101 Aug 12 '14 at 20:48
  • Thank you, this sounds like a feasible reason :-) – Bergi Aug 12 '14 at 20:55
-3

This is a case of pseudorandom number generation vs. random generation. Basically, there are numbers that will occur more often than others when you generate pseudorandom numbers (such as with the Math.random() function). See here for more information about the difference.

As far as actually making it look more "random", I would note that for a smaller range of i the image does look random, it's only when you choose a very large value that the flaws become apparent. Additionally, I don't believe seting your own seed for Math.random will be an adequate solution either, because you will still see degradation in the "randomness" when you iterate a very large number of times.

A potential solution would be to use a different library to generate pseudorandom numbers and see if it produces a better looking output. Other than that, you're pretty much constrained to the deterministic properties of computers (at least until powerful quantum computers show up on the market!).

Edit - This problem is unique to Google Chrome's implementation of Math.random() and documented in the following locations: Why is Google Chrome's Math.random number generator not *that* random? https://code.google.com/p/chromium/issues/detail?id=276886 https://code.google.com/p/v8/issues/detail?id=558

Community
  • 1
  • 1
Erik
  • 71
  • 1
  • 7
  • Numbers that occur more often than others? No, the implementation would need to be severly f**ed up for that. Numbers that occur in patterns (that become visible when for example painting images), yes that might happen when poor algorithms are used. – Bergi Aug 12 '14 at 20:02
  • @Bergi as this error only is reported in Chrome, it appears that although random (see http://xkcd.com/221/) there is something screwed up with the random number generator. Some numbers are indeed more likely than others. – Erik Aug 12 '14 at 20:08
  • Looking at the code, the issue is correlations between adjacent calls to Math.random(). You can play games filtering specific bits from the generator and the problem persists. The additional call each time appears to work. – jimm101 Aug 12 '14 at 20:22
  • @Erik: Both those bug reports you linked discuss a low *entropy* of V8's `random()` function. However, your first paragraph suggest that the *distribution* would be non-uniform - which is not the case. – Bergi Aug 12 '14 at 20:27
  • As noted in documentation "The random number generator is seeded from the current time" so perhaps it is the additional time between calls that makes the difference? Also, this doesn't explain why the code only fails in Chrome, highlighing a problem with how it generates random numbers. – Erik Aug 12 '14 at 20:32
  • @bergi https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random – Erik Aug 12 '14 at 20:40
  • @Erik: Those docs are specific to Mozilla's implementation. Also you need to understand how seeding works, multiple calls will typically use the same PRNG which was seeded at the time of the first call. – Bergi Aug 12 '14 at 20:46
  • To be clear, the frequency of occurrence wasn't the issue. If you take the OP's code and make y=x+.00001, you get a straight line--so the issue is that back-to-back calls to Math.random() are correlated, and therefore they fall on a straight line in the OP's use case. If the OP had used a counter, every number would have appeared once, but the cross-correlation would have been 1, and there would clearly be no randomness. Even with back-to-back calls there is still some very minor residual correlation--but the requirement to "look random" is still met. – jimm101 Aug 14 '14 at 16:29