How does Math.random() work?
Published: 2020-01-13 21:30:32

## Prolonged Prologue

Recently I worked on a stateless server. In other words, if and when it sends a second response to a client, it has no context of the first one.

Such backend code is pretty great – simple, clean, and easily testable.

Auditing or debugging? Not so great. Within a certain timeframe the backend may serve many clients and though there's enough information to reconstruct which response originated from which client, <mark>we're lazy and just wanted to "color" them</mark> for quick identification.

We decided to make the frontend generate a (pseudo-)random string when starting-up and send it with each request. No need for a convoluted UUID or something similar. Just plain ol' `Math.random().toString(36).slice(2)`.

## Fat Chance

During code review I explained to my colleague that 99.9% of the time it will make our lives easier and the 0.1% chance of 2 clients generating the same string is no big deal, because as explained, we can still distinguish between them like we did before.

She approved by change, got up, and as she walked away she pondered aloud _<q>But it's not really 0.1%, is it? Would be nice to figure out the **actual** chance of collision</q>_.

## Down the Rabbit Hole

I knew `Math.random` returns numbers between 0 (inclusive) and 1 (exclusive) with roughly equal probabilities across that range, I wasn't sure however _how_ it does that.

* First stop – MDN of course! [Their documentation for Math.random](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random) informed me that _<q>numbers in JavaScript are IEEE 754 floating point numbers</q>_. IEEE 754? What's that about exactly?

* Second stop – ECMAScript Spec. [The Number type section](https://www.ecma-international.org/ecma-262/5.1/#sec-8.5) revealed that IEEE 754 is just a fancy way of saying double-precision 64-bit floating-point number. Frankly, this is still too fancy, so I headed elsewhere.

* Third stop – Wikipedia. [The double-precision article](https://en.wikipedia.org/wiki/Double-precision_floating-point_format) threw me back to my CS degree with terms such as endianness and more importantly significand (AKA mantissa).

  * The last two sources taught me that even though this format has 2<sup>64</sup> possible values (duh!), reserving 3 of them to represent `-0` (which is different from `0`, mind you), `infinity`, and `-infinity`, is pocket change relative to the 2<sup>53</sup> `NaN` values. Yep, you read that right: given arbitrary sets of 64 bits, if you ask _<q>what number does this represent?</q>_, 1 out of 2048 times the answer will be _<q>it's **not** a number</q>_. 🤯 #MindBlown

 * Speaking of possible values, every non-zero number can take the shape of `± 2ⁿ × 1.something`. For example 2020, the current year, is `2¹⁰ × 1.97265625`. The benefit here is that the "1." part can be assumed and doesn't need to be stored. Thus the significand has an extra bit – making the number a _bit_ more precise. 😂 #DadJokes

At this stage I stopped reading in order to experiment what numbers can JavaScript store. The smallest one below `1` turns out to be `0.9999999999999999`. i.e. if you enter `0.99999999999999994` in the console, JS will omit the last digit, and if you enter `0.99999999999999995` it will just round up to `1`.
The next numbers are:
`0.9999999999999998`
`0.9999999999999997`
`0.9999999999999996`
`0.9999999999999994`
`0.9999999999999993`
`0.9999999999999992`
`0.9999999999999991`
`0.999999999999999`

`0.9999999999999995` is not absent by mistake. Remember these numbers are displayed as decimals, but are binary under the hood. Expect rounding errors when "translating" back and forth.

Naïvely I thought, _<q>Well, if I continue with these small decrements, after about 10 quadrillion times, it will go down to `0.0000000000000001`</q>_. I immediately realized this misses the whole point of floating-point! 😂 #DadJokes

It's not the end. From there, we can **again** decrement 10 quadrillion times
`0.00000000000000009999999999999999`
`0.00000000000000009999999999999997`
down to
`0.00000000000000000000000000000001`
and so on.

This revelation – the density increases towards 0 – is in fact tied to the [subnormal numbers](https://www.google.com/search?q=subnormal+numbers) (that "1.something" from before? for them it's actually "0.something").

I'm dwelling on this because `Math.random` is supposed to return values with approximately uniform distribution. This means the set of its possible results is **smaller** than the general set of numbers JS can represent in the range [0,1). Or looking at it the other way around: there are fractions that you can set yourself, but can never get from `Math.random`.

## Back on Track

* Penultimate stop – [The V8 blog](https://v8.dev/blog/math-random) explained how about 4 years ago `Math.random` switched to use the `xorshift128+` algorithm (noting other major browsers switched to it as well). This is _almost_ what I was looking for – as this algorithm deals with generating `integer` numbers.

* Final stop – [The glorious V8 source code](https://github.com/v8/v8/blob/52f88e1b937a46cb39087149a76615ced7e539f0/src/base/utils/random-number-generator.h#L111) unveiled how it's done (I believe other engines behave similarly): `ToDouble` takes the latest generated integer, right-shifts it into what would shortly become the significand, sets the exponent to `0x3FF` (which means `+2⁰`) and casts it to `double`. This yields `2⁰ × 1.random` and the only thing left to do is subtract `1`.

```cpp
  static inline double ToDouble(uint64_t state0) {
    // Exponent for double values for [1.0 .. 2.0)
    static const uint64_t kExponentBits = uint64_t{0x3FF0000000000000};
    uint64_t random = (state0 >> 12) | kExponentBits;
    return bit_cast<double>(random) - 1;
  }
```

## Answer to the Ultimate Question

There are 2⁵² (or 4,503,599,627,370,496) possible values for `Math.random` to return. It _is_ a few quadrillions after all!

I plugged this value into the [general equation for the birthday paradox](https://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem) and was relieved to learn that even with thousands of simultaneously connected clients, we have better chance of winning the lottery than have a collision.

## Post Trauma

I obviously called my colleague to share these findings with her. She nodded understandingly, then paused for a moment before remarking _<q>Good, now we also know the chance of an empty identifier</q>_.

To which I replied, _<q>Say what now?</q>_.

_<q>Yeah, there's 1 in 2⁵² chance to get any specific value from calling `Math.random()` and one of those is 0. In that rare yet possible case `slice(2)` will leave you with an empty string. Not that it matters too much – you said you wanted to "color" the traffic with a string. I guess **transparent** is as good color as any</q>_.

_<q>I'm never asking for your code review again.</q>_

---

📟 Let me know if you ever use `Math.random()` and get 0.