Discussion on: 10 Practical JavaScript Tricks

[Rafi]

Love seeing the "weird" parts of JavaScript. Can you elaborate on the Shuffle, where the '- 0.5' comes from?

[David Lorenz]

The sort function sorts before/after by checking negative vs positive numbers (0 means equal). Since random gives back anything between 0 to 1 you would never have a negative number. So you just simply substract -0.5 .

[Zach]

I think this is wrong though?
Since random is exclusive of 1, you're going to be slightly biased towards negatives, and thus not totally uniform (assuming that's the goal which 0.5 implies), right?

Maybe it should be Math.floor(Math.random() + 1) - 0.5
I think...

[David Lorenz]

Your proposed code always returns 0.5 since you floor a number x with 1 <= x < 2 which floored always gives 1 and therefore 1 - 0.5 = 0.5 so I do not think your solution would lead to anything useful in this case since it would not shuffle at all :)

The JS spec says:

Returns a number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or
pseudorandomly with approximately uniform distribution over that range, using an implementation-dependent
algorithm or strategy. This function takes no arguments.

That means we can trust the uniformity of it EXCLUDING the exact number 1 but including 0. So your argument is that we miss out on non-uniformity because it can only reach 0.99999999999999999 but in fact from a mathematical perspective this is the same number as 1. Not just mathematically but also in fact 0.99999999999999999 == 1 in JavaScript. Even if it was not (just theoretically) then the missing bit would be so extremely small that it would essentially become insignificant.

[Zach]

Oops, I should have said Math.floor(Math.random() * 2)

But I'm still not convinced of your argument. I agree that it is most likely insignificant, (considering the PRNG is essentially a black box and I don't even know if it is a standard implementation across all engines, and if it is it probably is not uniform to begin with). Add to the fact that we are dealing with FP and not continues numbers also muddies the water. But all else being equal, we would have a bias because the random function is not inclusive. But then again on a second though, the sort function would also return the same for 0.5 as it would for 0.5 + ε so that effectively gives you a uniform range of values.

For what it's worth, I tried running it in V8 (billions of times) but couldn't discern any patterns either way (but I was just seeing if the average was above or below 0 and logging the output; it would be interesting to investigate it further with proper statistical analysis.)

[David Lorenz]

Hey Zach. Maybe if you "mistrust" it then you rather first read the JS specs. The Engines are not allowed to interpret the distribution differently since they are spec based.

Your arguments are, sorry to say, invalid since the uniformity for the random function is given and due the to equalness of 0.99999999999999999 == 1 and the INEQUALNESS of 0.00000000000000001 == 0 . So there is your missing bit. Your so-called Epsilon does not exist since this is there is no more Epsilon than this. I just wrote the minimum and maximum numbers the Math.random returns.

Also again you probably meant with your example Math.floor(Math.random() * 2) - 1 since you are trying to have a "real" integer 1 inclusion but this does not change anything since from a mathematical perspective the distribution does not change with a factor for this sample since the factor is strictly linear.

Also if you have a "general" mistrust in the Math.random function then this is totally fine because it is "not really" random. There is the WebCrypto API which tries to provide way better randomized values.

[Zach]

I'm not sure what you mean by check the spec (or "mistrust")? There is no PRNG spec, it is entirely up to the engine. That means it depends on the environment you run your code in. For this discussion it is a black box and different black boxes have different implementations. Different implementations will have different uniformity. That alone makes this whole discussion pointless.

Second, you are still acting like we are working with continuous numbers. We are not. There is a finite set of numbers in JavaScript between 0 and 1. You could enumerate them like {a, b, c, d, ...}.

It's easy to create a general case where you have X numbers in your set. If you split the set in half, the halfs will either be equal (cardinality wise) or not (depending if X is even or odd). If they are not equal then any time you uniformly choose a number from the entire set, you will choose the larger set more often.

If you deny this then you are denying simple math. And this is exactly my point. This changes if you are dealing with continuous numbers (but we are not). We are splitting a finite set of numbers into two sets and choosing a set based on if it contains a number or not.

[David Lorenz]

I am not sure what you are trying to say since it was about the uniformity and you questioned first the approach in itself since the 0.00000000000000001 is missing because 1 is never reached. So I tried simply telling you that 1 is reached and therefore the initial argument does not count since even though the exact number 0.99999999999999999 is mathematically not the same (as it does not have infiinite 9) it is in fact in JavaScript. But in fact 0.9repeating is the same as 1 mathematically en.wikipedia.org/wiki/0.999...

Then you were providing something as static 0.5 and then providing a solution that just does the same as what the author proposed but times 2 and therefore not really changing anything but the overall interval.

This feels like you are jumping into more and more topics also because you compare Maths with JS but JS only has a subset of what actual Maths provide (e.g. precision wise) so ACTUAL maths 1:1 compared to JS do not really fit since not all theories apply exactly the same.

When I was talking about "mistrust" I was talking about the fact that you mistrust the uniformity of the PRNG in Math.random because you say that the approach of the author shall not be used although I try to argue that for shuffling an array it is very much helpful and sufficient.

Also you could actually check the sourcecode of V8. If you are coding for browsers you can check WebKit, V8 and SpiderMonkey. For node.js you can do the same.

E.g. for WebKit trac.webkit.org/browser/webkit/

By checking those sourcecodes you could decide if they fit your - apparently weirdly rare - use-cases. Or in other words: What use-case are you trying to solve so maybe that helps better treating the problem that you apparently have.

So I am unsure what problem you are trying to solve right now or if you are just trying to rant to be honest.

If you want a better random generator then go for the WebCrypto API. I am out and will not longer respond to this weirdly side-escalating discussion.

[Zach]

First, this is all hypothetical. I already agreed that is doesn't matter.

But you are wrong in your premise. Assuming the PRNG was perfectly uniform, the fact that 1 is not included in the interval DOES AFFECT the shuffling. It doesn't matter that 0.999999 = 1.

Let's make the assumption that the PRNG is ideally uniform (otherwise nothing else matters).
Then let's make a list of every number that can be represented in JavaScript as an IEEE754 double precision FP number (which is what Math.random() returns)

The set is written in hex, but it starts like

0x0000000000000001 = 4.94065645841246544176568792868E-324

0x0000000000000002 = 9.88131291682493088353137585736E-324
...
0x3FEFFFFFFFFFFFFF = 9.99999999999999888977697537484E-1 (closest number to 1 before 1)
0x3FF0000000000000 = 1

set a = {
0x0000000000000001, 0x0000000000000002, 0x0000000000000003, 0x0000000000000004, ....
0x3FEFFFFFFFFFFFFF
}

set b = {
0x0000000000000001, 0x0000000000000002, 0x0000000000000003, 0x0000000000000004, ....
0x3FEFFFFFFFFFFFFF, 0x3FF0000000000000
}

Do you see how set a excludes 1, and set b includes 1?
Now split each set into two 1/2 sets where each half set as equal cardinality (if possible)

Do you agree that the two halves of set a are different than the two sets of set b?

Now, randomly pick any number from the entire sample space. Then choose the half set from a that contains the number, and choose the half set from b that contains the number. Guess what, you will pick the 1/2 set with the more numbers more times than the half set with the less numbers.

This is why it matters if 1 is included. You keep saying that 0.99999999=1 but that doesn't mean anything. In fact, it less than meaningless because all you are saying is the decimal value 0.99999999 is represented as 1 as a 64-bit FP number. You are conflating the decimal representation with the in-memory representation. We are dealing with finite sets of discrete numbers.

My original argument was that sorting using the described method will result in a biased sort.
I have since said that it doesn't matter because even assuming the PRNG was perfectly uniform the bias would be insignificantly small, and even more so, it doesn't matter because the PRNG is a black box that is most likely far from perfectly uniform.

But my original statement is correct. Excluding 1 changes the behavior, unless that change is accounted for.

And you are most likely correct that my solution was not an improvement. The first one was 100% wrong, the second might not do anything because it still has the built flaw of not including 1 in the original random number. But my point wasn't to solve the problem, just to show that it won't result in a uniform sort.