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

Question

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?

Answer 1

Math.random() * n will not result in a number greater or equal to n because the Math.random() returns a floating point number x where 0 <= x < 1. The documentation for the Math.random() function is here

Answer 2

If n is greater than the minimum positive normal number of the floating-point format, then Math.Random()*n < n.

(As abacabadabacaba noted in a comment, if n is the minimum normal, e.g., 2⁻¹⁰²² for IEEE-754 basic 64-bit binary, and Math.Random returns its maximum value, 1 − 2⁻⁵³, then the product rounds to the minimum normal, so 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•2^1−p is the value represented by the low bit and is the ULP for the represented number, and h•2^−p 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 2^m•(1−2^−p) ≤ n < 2^M+1•(1−2^−p), 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-nearest-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 x₀ < x₁, then x₀•y < x₁•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−2^−p.

By Lemma 1, if g*n < n, any result x ≤ g 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 greater than the minimum normal number of the floating-point format, then g•n is exactly representable in the floating-point format, and there is no rounding, so g*n = (1−2^−p)•n < n. If n is not a power of two, then g•n is (1−2^−p)•n = n − n•2^−p. 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•2^1−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.

Answer 3

The answer is yes, but only in very extreme cases.

It is possible for

Math.random()*n >= n

To return true in cases where n is extremely large.

Note that in these cases, the result will equal the chosen number n.

From the Math.random() documentation:

Note that as numbers in JavaScript are IEEE 754 floating point numbers with round-to-nearest-even behavior, the ranges claimed for the functions below (excluding the one for Math.random() itself) aren't exact. If extremely large bounds are chosen (253 or higher), it's possible in extremely rare cases to calculate the usually-excluded upper bound.

function getRandomArbitrary(min, max) {
  return Math.random() * (max - min) + min;
}

Although technically possible, this occurrence is so very rare as to be negligible

Answer 4

I just want to add something that might be usesul to know, actually if n is set to Number.POSITIVE_INFINITY the condition becomes true:

let posInf = Number.POSITIVE_INFINITY;
console.log(Math.random(), posInf);
console.log(Math.random() * posInf >= posInf);