# For a positive integer n, is Math.random()*n >= n possible?

• A+
Category：Languages

According to Why are floating point numbers inaccurate?, floating point numbers has errors.

My question is, for a positive integer n, is it possible that Math.random()*n has errors such that its result becomes equals or greater than n?

If n is in the normal range of the floating-point format, then `Math.Random()*n` < n.

A proof follows.

## Preliminaries

• In this answer, expressions written in `code format` refer to computed values. Expressions outside code format refer to exact mathematics. For any number n, `n` is the result of rounding n to the floating-point format. `a``b` is the exact mathematical product of `a` and `b` before floating-point rounding, and `a*b` is the floating-point result after rounding.
• IEEE-754 binary floating-point with rounding-to-nearest-ties-to-even is used. Some familiarity with IEEE-754 is required.
• ULP stands for Unit of Least Precision. It is the value of the least significant bit of the significand of a floating-point representation of a particular number.
• p is the number of bits in the significand of a floating-point representation. For IEEE-754 basic 64-bit binary floating-point, p is 53, but this proof applies to other widths.
• If h is the value represented by the high bit of the significand in a normal floating-point representation (due to scaling by the exponent), h•21−p is the value represented by the low bit and is the ULP for the represented number, and h•2p is ½ ULP and is the maximum change that can be produced by rounding any number in the range of this exponent to the floating-point format.
• By “n is in the normal range,” I mean `n` is normal. This means 2m•(1−2p) ≤ n < 2M+1•(1−2p), where m and M are the minimum and maximum exponents in the floating-point format (−1022 and 1023 for IEEE-754 64-bit binary floating-point).

## Lemma 0: Rounding is Weakly Monotonic

Given a < b, consider the results of rounding them to the floating-point format, `a` and `b` (using the round-to-neaest-ties-to-even rule).

Suppose `b` < `a`.

If `a`a, then `b` < `a`a < b. This is not possible because `b` is farther from b than `a` is, so b must round to `a` or a closer number, not to `b`. Conversely, if a < `a`, then a`b` < `a` or `b` < a < `a`. In the former case, a could not round to `a` as `b` is closer. In the latter case, if `a`b, then b cannot round to `b` since `a` is closer, and, if b < `a`, then a cannot round to `a` since `b` is closer.

So it cannot be that `b` < `a`; it must be that `a``b`.

## Lemma 1: Floating-Point Multiplication is Weakly Monotonic

Multiplication by a positive number y is weakly monotonic, since, if x0 < x1, then x0•y < x1•y, and Lemma 0 tells us that `x0*y``x1*y`.

## Proof

Let g be the greatest possible result of `Math.Random()`. Since JavaScript’s `Math.Random()` returns a number in [0, 1), g is 1−2p.

By Lemma 1, if `g*n` < n, any result xg of `Math.random()` satisfies `x*n` < n.

We will prove that `g*n` < `n` and then show this implies `g*n` < n.

Consider `g*n`. If `n` is exactly a power of two, then `g``n` is exactly representable in the floating-point format, and there is no rounding, so `g*n` = (1−2p)•`n` < `n`. If `n` is not a power of two, then `g``n` is (1−2p)•`n` = `n``n`•2p. The latter is less than `n` by more than ½ ULP of `n`, and so, when it is rounded to the floating-point format, it is rounded down, producing a result less than `n`. (Note this is not true for any number n, since `g*n` could be in the subnormal range, where an ULP may be larger than `n`•21−p. However, we assume n is in the normal range, which is true for all positive integers up to the point where `n` overflows.)

Thus `g*n` < `n`. Finally, we consider the possibility that, when n is rounded to the floating-point format, the result `n` is greater than n, and this could lead to `g*n` > n. However, `g*n` < `n` requires that `g*n` be less than `n` by at least 1 ULP, but rounding n to `n` can increase the value by at most ½ ULP. So `g*n` < n.