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. ab 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 aa, then b < aa < 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 ab < a or b < a < a. In the former case, a could not round to a as b is closer. In the latter case, if ab, 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 ab.

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*yx1*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 gn 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 gn is (1−2p)•n = nn•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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: