- A+

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*•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-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 *x*_{0} < *x*_{1}, then *x*_{0}•y < *x*_{1}•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, 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*.