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

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 2

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