对于正整数n,Math.random()*n> = n可能吗？

Question

根据为什么浮点数不准确？,浮点数有错误.

我的问题是,对于正整数n,Math.random()*n是否有错误使其结果等于或大于n？

Answer 1

Math.random() * n不会导致数字大于或等于n因为Math.random()返回浮点数x所在0 <= x < 1.该Math.random()功能的文档在这里

Answer 2

如果n大于浮点格式的最小正正规数，则Math.Random()*n< n。

\n

（正如abacabadabacaba在评论中指出的，如果n是最小法线，例如 2 ^{\xe2\x88\x921022}对于 IEEE-754 基本 64 位二进制，并Math.Random返回其最大值，1 \xe2\x88\x92 2 ^{\xe2 \x88\x9253}，然后乘积舍入到最小法线，因此Math.Random()*n= n。）

\n

下面是一个证明。

\n

预赛

\n

\n
• 在这个答案中，编写的表达式code format指的是计算值。代码格式之外的表达式指的是精确的数学。对于任何数字n，是将n舍入为浮点格式n的结果。\xe2\x80\xa2是浮点舍入前与浮点舍入前的精确数学乘积，是舍入后的浮点结果。ababa*b
\n
• 使用具有舍入到最接近偶数的 IEEE-754 二进制浮点。需要熟悉 IEEE-754。
\n
• ULP 代表最低精度单位。它是特定数字的浮点表示形式的有效数的最低有效位的值。
\n
• p是浮点表示形式的有效数中的位数。对于 IEEE-754 基本 64 位二进制浮点，p为 53，但此证明适用于其他宽度。
\n
• 如果h是普通浮点表示中有效数的高位表示的值（由于按指数缩放），则h \xe2\x80\xa22 ^{1\xe2\x88\x92 p}是由低位 是所表示数字的 ULP，h \xe2\x80\xa22 ^{\xe2\x88\x92 p}是 \xc2\xbd ULP，是通过舍入此范围内的任何数字可以产生的最大变化浮点格式的指数。
\n
• \xe2\x80\x9c n在正常范围内，\xe2\x80\x9d 我的意思n是正常。这意味着 2 ^m \xe2\x80\xa2(1\xe2\x88\x922 \ ^{xe2\x88\x92 p} ) \xe2\x89\xa4 n < 2 ^{M +1} \xe2\x80\xa2(1\xe2\x88 \x922 ^{\xe2\x88\x92 p} )，其中m和M是浮点格式的最小和最大指数（IEEE-754 64 位二进制浮点为 \xe2\x88\x921022 和 1023）。
\n

\n

引理 0：舍入是弱单调的

\n

给定a < b，考虑将它们舍入为浮点格式的结果，a并且b（使用舍入到最近的偶数规则）。

\n

假设b< a.

\n

如果a\xe2\x89\xa4 a，则b< a\xe2\x89\xa4 a < b。这是不可能的，因为b比 离b更远a，因此b必须四舍五入到a或更接近的数字，而不是四舍五入到b。相反，如果a < a，则\ xe2\x89\xa4 b<a或b< a < a。在前一种情况下，a无法舍入a为b更接近的值。在后一种情况下，如果a\xe2\x89\xa4 b，则b不能舍入b为 因为a更接近，并且，如果b < a，则a不能舍入为a因为b更接近。

\n

所以不可能是b< a; 一定是a\xe2\x89\xa4b。

\n

引理 1：浮点乘法是弱单调的

\n

乘以正数y是弱单调的，因为如果\n x ₀ < x ₁，则x ₀ \xe2\x80\xa2y < x ₁ \xe2\x80\xa2y，\n引理 0 告诉我们x0*y\xe2\ x89\xa4x1*y。

\n

证明

\n

令g为 的最大可能结果Math.Random()。由于 JavaScript\xe2\x80\x99sMath.Random()返回 [0, 1) 中的数字，因此g为 1\xe2\x88\x922 ^{\xe2\x88\x92 p}。

\n

根据引理 1，如果g*n< n，任何结果x \xe2\x89\xa4 g满足< nMath.random()x*n。

\n

我们将证明g*n<n然后证明这意味着g*n< n。

\n

考虑g*n。如果n正好比浮点格式的最小正常数大 2 的幂，则g\xe2\x80\xa2n可以准确地用浮点格式表示，并且不进行舍入，因此g*n= (1\xe2\ x88\x922 ^{\xe2\x88\x92 p} )\xe2\x80\xa2 n< n. 如果n不是 2 的幂，则g\xe2\x80\xa2n为 (1\xe2\x88\x922 ^{\xe2\x88\x92 p} )\xe2\x80\xa2 n= n\xe2\x88\x92 n\xe2\x80\ xa22 ^{\xe2\x88\x92 p}。后者比 的n\xc2\xbd ULP 小n，因此，当它舍入为浮点格式时，它会向下舍入，产生小于 的结果n。（请注意，这对于任何数字n都是不正确的，因为g*n可能在次正常范围内，其中 ULP 可能大于n\xe2\x80\xa22 ^{1\xe2\x88\x92 p}。但是，我们假设n处于正常范围内范围，对于所有正整数都成立，直到n。）

\n

因此g*n< n. 最后，我们考虑以下可能性：当n舍入为浮点格式时，结果n大于n，这可能导致g*n> n。但是，g*n<n要求g*n至少小于n1 ULP，但将nn舍入到最多可以将该值增加 \xc2\xbd ULP 。所以g*n< n。

\n