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.
- In this answer, expressions written in
code formatrefer to computed values. Expressions outside code format refer to exact mathematics. For any number n,
nis the result of rounding n to the floating-point format.
bis the exact mathematical product of
bbefore floating-point rounding, and
a*bis 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•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
nis normal. This means 2m•(1−2−p) ≤ n < 2M+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,
b (using the round-to-neaest-ties-to-even rule).
a ≤ a, then
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 <
a. In the former case, a could not round to
b is closer. In the latter case, if
a ≤ b, then b cannot round to
a is closer, and, if b <
a, then a cannot round to
b is closer.
So it cannot be that
a; it must be that
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
Let g be the greatest possible result of
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
x*n < n.
We will prove that
n and then show this implies
g*n < n.
n is exactly a power of two, then
n is exactly representable in the floating-point format, and there is no rounding, so
g*n = (1−2−p)•
n is not a power of two, then
n is (1−2−p)•
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•21−p. However, we assume n is in the normal range, which is true for all positive integers up to the point where
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,
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.