8

Random.NextDouble()（范围 [0.0,1.0) 中的 Double）有时与大的 Int64 相乘（让 Int64 big = 9000000000L），结果下限以获得比从 Random 获得的值更大的随机 Int64 值.Next()（范围 [0,Int32.MaxValue) 中的 Int32）。

Random r = new Random();
long big = 9000000000L;
long answer = (long) (r.NextDouble() * big);

在我看来，[0.0, 1.0) 范围内 Double 的唯一值总数为其可能生成的唯一 Int64 数量提供了上限。事实上，一个宽松的上限，因为许多不同的 Double 将映射到同一个 Int64。

因此，我想知道：[0.0, 1.0) 范围内双精度的唯一值总数是多少？

如果你能告诉我“大”可以取的最大值是多少，这样“答案”可以是 [0,big) 范围内的一个值，以及“答案”的值的分布是否均匀，那就更好了，假设Random.NextDouble() 是统一的。

编辑：这里的 Double (double) 指的是 IEEE 754 浮点双精度，而 Int64 (long) 和 Int32 (int) 分别指的是 64 位和 32 位有符号 2 的补码。

受这个问题的启发：Generating 10 digits unique random number in java

当我使用 C# 时，这个问题与语言无关，更多的是关于离散数学而不是编程，但它困扰我的主要不是数学上的好奇心，而是一个程序员想要使用公式，只有当它做它的时候应该这样做，并且从安全的角度来看。

4

6 回答 6

7

IEEE-754 有 11 位指数和 52 位尾数。假设符号位为 0（正），如果指数范围从 0x001 到 0x3FE，则该值是 0 到 1 之间的标准浮点数。尾数以不存储的前导 1 进行解释。对于指数的这些 0x3FE 值中的每一个，尾数都有 2^52 个值。此外，如果指数为 0x000，则尾数被解释为没有该前导值，但就好像指数为 0x001，总共 0x3FF = 1023 个指数，其中所有尾数均有效。这是总共1023*2^52 个值。另外，负0也可以算，多一个值。

如果从所有值均匀地生成随机双精度数，那么在相乘以生成 Int64 时，这确实会产生偏差。但是，任何合理的随机库都会在 [0, 1) 上近似均匀分布，这在将其转换为 Int64 时不会有偏差。允许生成 [0, big) 中的所有整数的“大”的最大值是 2^53——1/2 和 1 之间的 2^52 数字的分辨率是 2^(-53)。但是，通常情况下，这些数字是通过将随机整数除以整数范围（通常是 Int32）来产生的，这意味着您实际上不能产生比这个来源更多的数字。考虑直接组合两个 Int32，例如将 1 移位 32 位并将它们组合成一个 Int64。（但要小心——生成器的状态空间可能只有 32 位。）

于 2011-03-18T10:58:44.987 回答
5

作为您问题的必然结果，我将告诉您RandomC# 生成器在内部使用了一个生成器，该生成器在0...Int32.MaxValue - 1. 然后它将数字除以Int32.MaxValue（从技术上讲，它乘以该数字的倒数）以返回一个双精度数。所以在 C# 中，只有Int32.MaxValue可能的双精度返回 ( 0...Int32.MaxValue - 1)

于 2011-03-18T09:58:15.643 回答
3

IEEE754 非常清楚双精度：

http://en.wikipedia.org/wiki/IEEE_754-2008

你有 52 位精度加上一个额外的假设位。

您有从 -1022 到 1023 的指数，大约 11 位，包括一个符号。

第 64 位是数字的总符号。

我们将忽略次规范化的数字。

您询问的是 -1022 和 0 之间的指数。这意味着您有大约 10 位可用的 11 位指数可供您使用。

您有 52+1 位可用尾数。

这大约是 62 位的可用精度来表示 2**62 个不同的值

在此处输入图像描述

于 2011-03-18T11:08:39.233 回答
1

@wnoise 几乎做到了，但这是我的两分钱。

IEEE 浮点数可以作为整数进行比较和递增，但有一些限制，有关详细信息，请参阅此问题。因此，如果我们将 +0.0 和 1.0 转换为 64 位整数，我们会得到介于 0 和 1 之间的步数：

#include <iostream>

int main()
{
        double zero = 0.0;
        double one = 1.0;
        unsigned long long z = *reinterpret_cast<unsigned long long*>(&zero);
        unsigned long long o = *reinterpret_cast<unsigned long long*>(&one);
        std::cout << z << std::endl;
        std::cout << o << std::endl;
}

这分别给了我 0 和 4607182418800017408，即在 [0.0, 1.0) 范围内有 4607182418800017408 个唯一的双精度值。

于 2011-03-18T11:39:24.943 回答
0

a 在 [0.0, 1.0) 范围内的唯一值的总数double取决于double特定环境中的表示。

最常见的表示之一是IEEE 754指定的表示。该格式是由Java和C#强制要求的（参见1.3 类型和变量以了解后者）。

于 2011-03-18T09:47:55.523 回答
0

这取决于 . 的实现double。有些实现不允许非规范化值并省略前导值；在这里确定可能值的数量很容易：

  • 有一些“特殊”值（0、+0、-0、+∞、-∞、静默 NaN、信号 NaN）通常会花费你一个可能的指数
  • 移动尾数和修改指数是不可能给出等价的数字的

如果您的实现允许非规范化值，那么确定这个数字会变得有点困难，但我会首先将此表示中的可能值映射到具有固定前导值的等效表示（在尾数中使用少一点）；如果您找到了合适的映射，这将是单射的，并且您已将问题简化为更简单的问题。

于 2011-03-18T10:09:00.460 回答