如何使用 random()={0..1} 生成任意范围内的数字并保持均匀性和密度？

Question

生成 [x..y] 范围内的随机数，其中 x 和 y 是任意浮点数。使用函数 random()，它从 P 个均匀分布的数字（称为“密度”）中返回 [0..1] 范围内的随机浮点数。必须保持均匀分布，并且 P 也必须按比例缩放。

我认为，此类问题没有简单的解决方案。为了简化一点，我问你如何生成一个区间 [-0.5 .. 0.5] 中的数字，然后是 [0 .. 2] 中的数字，然后是 [-2 .. 0] 中的数字，同时保持均匀性和密度？因此，对于 [0 .. 2]，它必须从 P*2 个均匀分布的数字中生成一个随机数。

显而易见的简单解决方案 random() * (x - y) + y 不会生成所有可能的数字，因为所有 abs(xy)>1.0 情况的密度较低。许多可能的值将被错过。请记住，random() 仅返回 P 个可能数字中的一个数字。然后，如果你将这个数字乘以 Q，它只会给出 P 个可能值中的一个，按 Q 缩放，但你也必须按 Q 缩放密度 P。

Answer 1

如果我很好地理解你的问题，我会给你一个解决方案：但我会从范围中排除 1, 。

N = numbers_in_your_random // [0, 0.2, 0.4, 0.6, 0.8] will be 5

// This turns your random number generator to return integer values between [0..N[;
function randomInt()
{
    return random()*N;
}

// This turns the integer random number generator to return arbitrary
// integer
function getRandomInt(maxValue)
{
    if (maxValue < N)
    {
        return randomInt() % maxValue;
    }
    else
    {
        baseValue = randomInt();
        bRate = maxValue DIV N;
        bMod = maxValue % N;
        if (baseValue < bMod)
        {
            bRate++;
        }
        return N*getRandomInt(bRate) + baseValue;
    }
}

// This will return random number in range [lower, upper[ with the same density as random()
function extendedRandom(lower, upper)
{
    diff = upper - lower;
    ndiff = diff * N;
    baseValue = getRandomInt(ndiff);
    baseValue/=N;
    return lower + baseValue;
}

Answer 2

如果您确实想生成给定范围内具有统一数字密度的所有可能的浮点数，则需要考虑浮点格式。对于二进制指数的每个可能值，您都有不同的代码数字密度。直接生成方法需要显式处理这个问题，而间接生成方法仍然需要考虑它。我将开发一种直接方法；为了简单起见，以下内容专门指 IEEE 754 单精度（32-位）浮点数。

最困难的情况是任何包含零的区间。在这种情况下，为了产生完全均匀的分布，您需要将每个指数处理到最低值，再加上非标准化数字。作为一种特殊情况，您需要将零分为两种情况：+0 和 -0。

此外，如果您如此密切关注结果，则需要确保您使用的是良好的伪随机数生成器，并且具有足够大的状态空间，以便您可以期望它以接近均匀的概率命中每个值。这会取消 C/Unix rand() 以及可能的 *rand48() 库函数的资格；你应该使用类似 Mersenne Twister 的东西。

---

关键是将目标区间分解为子区间，每个子区间都由不同的二进制指数和符号组合覆盖：在每个子区间内，浮点代码均匀分布。

第一步是选择适当的子区间，其概率与其大小成正比。如果间隔包含 0，或者以其他方式覆盖较大的动态范围，则这可能需要大量随机位，直至可用指数的整个范围。

特别是，对于 32 位 IEEE-754 数，有 256 个可能的指数值。每个指数控制的范围是下一个较大指数大小的一半，但非标准化情况除外，其大小与最小正常指数区域相同。零可以被认为是最小的非规范化数；如上所述，如果目标区间跨过零，+0 和 -0 的概率也许应该减半，以避免其权重加倍。

如果选择的子区间覆盖由特定指数控制的整个区域，则所需要做的就是用随机位（23 位，对于 32 位 IEEE-754 浮点数）填充尾数。但是，如果子区间未覆盖整个区域，则您将需要生成仅覆盖该子区间的随机尾数。

处理初始和辅助随机步骤的最简单方法可能是将目标区间舍入以包括部分覆盖的所有指数区域的整体，然后拒绝并重试落在其之外的数字。这允许以简单的 2 次方概率生成指数（例如，通过计算随机比特流中前导零的数量），并提供一种简单而准确的方法来生成仅覆盖部分数字的尾数。指数区间。 （这也是处理 +/-0 特殊情况的好方法。）

作为另一种特殊情况：为了避免生成比它们所在的指数区域小得多的目标区间的低效生成，“明显简单”的解决方案将在事实上，对于这样的间隔，生成相当统一的数字。如果您想要完全均匀的分布，则可以通过仅使用足够的随机位来覆盖该子间隔来生成子间隔尾数，同时仍然使用上述拒绝方法来消除目标间隔之外的值。

Answer 3

好吧， [0..1] * 2 == [0..2] （仍然统一）

[0..1] - 0.5 == [-0.5..0.5]< /code> 等等，

不知道你在哪里经历过这样的面试？

更新：好吧，如果我们想开始关心乘法的精度损失（这很奇怪，因为不知何故你在原始任务中并不关心这一点，并假装我们关心“值的数量” ，我们可以开始迭代，为了做到这一点，我们还需要一个函数，它将返回 [0..1) 中均匀分布的随机值 - 这可以通过删除 来完成。 1.0 值会出现。之后，我们可以将整个范围分成足够小的等份，以便不关心精度的损失，随机选择一个（我们有足够的随机性来做到这一点），并使用 [0..1) 函数在这个桶中选择一个数字除最后一个之外的所有部分。

或者，您可以想出一种方法来编码足够多的值来关心，并且只需为此代码生成随机位，在这种情况下，您并不真正关心它是 [0..1] 还是只是 {0, 1} 。

Answer 4

让我重新表述一下您的问题：

让 random() 成为一个在 [0,1) 上具有离散均匀分布的随机数生成器。令 D 为 random() 返回的可能值的数量，每个值都比前一个精确地 1/D 大。创建一个在 [L, U) 上具有离散均匀分布的随机数生成器 rand(L, U)，使得每个可能值精确为 1/D< /code> 比之前的大。

——

一些简短的笔记。

1. 这种形式的问题，正如你所说，是无法解决的。那
   也就是说，如果 N = 1，我们无能为力。
2. 我不要求 0.0 成为 random() 的可能值之一。如果不是，那么当 U - L U - L U - L U - L U - L U - L U - L U - L U - L U - L 1/D。我并不特别担心这个案子。
3. 我使用所有半开范围，因为它使分析更简单。使用封闭范围很简单，但很乏味。

最后，好东西。这里的关键见解是，可以通过独立选择结果的整体和小数部分来维持密度。

首先，请注意，给定 random()，创建 randomBit() 很简单。也就是说

randomBit() { return random() >= 0.5; }

，如果我们想均匀地随机选择 {0, 1, 2, ..., 2^N - 1} 之一，使用 randomBit() 就很简单，只需生成每个位即可。将此称为random2(N)。

使用 random2() 我们可以选择 {0, 1, 2, ..., N - 1} 之一：

randomInt(N) { while ((val = random2(ceil(log2(N)))) >= N); return val; }

现在，如果 D已知，那么问题就很微不足道了，因为我们可以将其简化为简单地随机均匀地选择 floor((U - L) * D) 值之一，我们可以使用 randomInt( ）。

因此，我们假设 D 未知。现在，我们首先创建一个函数，以适当的密度生成 [0, 2^N) 范围内的随机值。这很简单。

rand2D(N) { return random2(N) + random(); }

rand2D() 是我们要求 random() 的连续可能值之间的差异精确为 1/D 的地方。如果不是，这里可能的值将不会具有均匀的密度。

接下来，我们需要一个函数来选择 [0, V) 范围内具有适当密度的值。这与上面的randomInt()类似。

randD(V) { while ((val = rand2D(ceil(log2(V)))) >= V); return val; }

最后...

rand(L, U) { return L + randD(U - L); }

如果 L / D 不是整数，我们现在可能已经偏移了离散位置，但这并不重要。

--

最后一点，您可能已经注意到其中一些函数可能永远不会终止。这本质上是一个要求。例如，random() 可能只有一位随机性。如果我要求您从三个值之一中进行选择，则您不能使用保证终止的函数统一随机地执行此操作。

Answer 5

考虑这种方法：

我假设基本随机数生成器在 [0..1] 范围内
生成数字

0, 1/(p-1), 2/(p-1), ..., (p-2)/(p-1), (p-1)/(p- 1)

如果目标区间长度小于等于1，
返回随机()*(yx) + x。

否则，将每个数字r从基本RNG映射到
目标范围：

[r*(p-1)*(yx)/p, (r+1/(p-1))*(p-1)*(yx)/p]

(即为每个 P 数字分配一个长度为 (yx)/p 的 P 间隔），

然后在该间隔中递归生成另一个随机数，
将其添加到间隔开始。

伪代码：

const p;

function rand(x, y)
  r = random()
  if y-x <= 1
    return x + r*(y-x)
  else
    low = r*(p-1)*(y-x)/p
    high = low + (y-x)/p
    return x + low + rand(low, high)

Answer 6

在真正的数学中：解决方案只是提供的：

return random() * (upper - lower) + lower

问题是，即使你有浮点数，也只有一定的分辨率。因此，您可以做的是应用上面的函数并添加另一个缩放到缺失部分的 random() 值。

如果我举一个实际的例子，我的意思就很清楚了：

例如，以 2 位精度从 0..1 获取 random() 返回值，即 0.XY，下限为 100，上限为 1100。

因此，通过上述算法，您可以得到结果 0.XY * (1100-100) + 100 = XY0.0 + 100。
你永远不会看到结果 201，因为最后的数字必须是 0。

这里的解决方案是再次生成一个随机值并将其添加 *10，这样你的精度就是一位数（这里你必须注意不要超出你给定的范围，这可能会发生，在这种情况下你必须丢弃结果并生成一个新的数字）。

也许您必须重复一次，频率取决于 random() 函数提供的位置数量以及您对最终结果的期望。

在标准 IEEE 格式中，精度有限（即双 53 位）。因此，当您以这种方式生成一个数字时，您永远不需要生成多个附加数字。

但你必须小心，当你添加新的数字时，不要超过给定的上限。有多种解决方案：首先，如果超出限制，则从新开始，生成新数字（不要切断或类似，因为这会改变分布）。

第二种可能性是检查丢失的较低位范围的间隔大小，并且
找到中间值，并生成一个适当的值，以保证结果适合。

Answer 7

您必须考虑每次调用 RNG 时产生的熵量。下面是我刚刚编写的一些 C# 代码，演示了如何从低熵源累积熵并最终得到高熵随机值。

using System;
using System.Collections.Generic;
using System.Security.Cryptography;

namespace SO_8019589
{
  class LowEntropyRandom
  {
    public readonly double EffectiveEntropyBits;
    public readonly int PossibleOutcomeCount;
    private readonly double interval;
    private readonly Random random = new Random();
    public LowEntropyRandom(int possibleOutcomeCount)
    {
      PossibleOutcomeCount = possibleOutcomeCount;
      EffectiveEntropyBits = Math.Log(PossibleOutcomeCount, 2);
      interval = 1.0 / PossibleOutcomeCount;
    }
    public LowEntropyRandom(int possibleOutcomeCount, int seed)
      : this(possibleOutcomeCount)
    {
      random = new Random(seed);
    }
    public int Next()
    {
      return random.Next(PossibleOutcomeCount);
    }
    public double NextDouble()
    {
      return interval * Next();
    }
  }

  class EntropyAccumulator
  {
    private List<byte> currentEntropy = new List<byte>();
    public double CurrentEntropyBits { get; private set; }
    public void Clear()
    {
      currentEntropy.Clear();
      CurrentEntropyBits = 0;
    }
    public void Add(byte[] entropy, double effectiveBits)
    {
      currentEntropy.AddRange(entropy);
      CurrentEntropyBits += effectiveBits;
    }
    public byte[] GetBytes(int count)
    {
      using (var hasher = new SHA512Managed())
      {
        count = Math.Min(count, hasher.HashSize / 8);
        var bytes = new byte[count];
        var hash = hasher.ComputeHash(currentEntropy.ToArray());
        Array.Copy(hash, bytes, count);
        return bytes;
      }
    }
    public byte[] GetPackagedEntropy()
    {
      // Returns a compact byte array that represents almost all of the entropy.
      return GetBytes((int)(CurrentEntropyBits / 8));
    }
    public double GetDouble()
    {
      // returns a uniformly distributed number on [0-1)
      return (double)BitConverter.ToUInt64(GetBytes(8), 0) / ((double)UInt64.MaxValue + 1);
    }
    public double GetInt(int maxValue)
    {
      // returns a uniformly distributed integer on [0-maxValue)
      return (int)(maxValue * GetDouble());
    }
  }

  class Program
  {
    static void Main(string[] args)
    {
      var random = new LowEntropyRandom(2);  // this only provides 1 bit of entropy per call
      var desiredEntropyBits = 64; // enough for a double
      while (true)
      {
        var adder = new EntropyAccumulator();
        while (adder.CurrentEntropyBits < desiredEntropyBits)
        {
          adder.Add(BitConverter.GetBytes(random.Next()), random.EffectiveEntropyBits);
        }
        Console.WriteLine(adder.GetDouble());
        Console.ReadLine();
      }
    }

  }
}

由于我使用的是 512 位哈希函数，因此这是您可以从 EntropyAccumulator 中获取的最大熵量。如果有必要的话，这个问题是可以解决的。

Answer 8

如果我正确理解你的问题，那就是 rand() 生成间隔精细但最终离散的随机数。如果我们将其乘以较大的 (yx)，则会以丢失 [x,y] 范围内的许多浮点值的方式分散这些精细间隔的浮点值。这样可以吗？

如果是这样，我想我们已经有了辩证法已经给出的解决方案。让我解释一下为什么他是对的。

首先，我们知道如何生成一个随机浮点数，然后向其中添加另一个浮点值。这可能会因加法而产生舍入误差，但只会出现在小数点最后一位。如果您想要更高的精度，请使用双精度数或具有更精细数值分辨率的东西。因此，考虑到这一点，问题并不比在 [0,yx] 范围内找到具有均匀密度的随机浮点数更难。假设 yx = z。显然，由于 z 是浮点数，因此它可能不是整数。我们分两步处理这个问题：首先生成小数点左边的随机数字，然后生成小数点右边的随机数字。均匀分布意味着它们的总和也均匀分布在 [0,z] 范围内。令 w 为 <= z 的最大整数。为了回答我们的简化问题，我们可以首先从 {0,1,...,w} 范围中选择一个随机整数。然后，步骤#2是将单位间隔中的随机浮点添加到该随机数。它不会与任何可能较大的值相乘，因此它具有与数字类型一样精细的分辨率。 （假设您使用的是理想的随机浮点数生成器。）

那么，随机整数是最大的（即 w）并且我们添加到其中的随机浮点数大于 z - w 的极端情况又如何呢？随机数超出允许的最大值？答案很简单：再次执行所有操作并检查新结果。重复此操作，直到获得允许范围内的数字。这是一个简单的证明，即均匀生成的随机数如果超出允许的范围，则被丢弃并再次生成，结果是在允许的范围内均匀生成的随机数。一旦您进行了这一关键观察，您就会发现辩证法满足您的所有标准。

Answer 9

当您使用 random() 生成随机数时，您会得到一个介于 0 和 1 之间的浮点数，其精度（或密度，随您而定）未知。

当您将其与数字 (NUM) 相乘时，您会失去此精度，即 lg(NUM)（基于 10 的对数）。因此，如果乘以 1000 (NUM=1000)，则会丢失最后 3 位数字 (lg(1000) = 3）。

您可以通过向原始数字添加一个较小的随机数（其中缺少 3 位数字）来纠正此问题。但你不知道精度，所以你无法确定它们到底在哪里。

我可以想象两种情况：

（X =范围开始，Y =范围结束）

1：您定义精度（PREC，例如20位数字，因此PREC = 20），并认为它足以生成随机数，因此表达式将是：

( random() * (Y-X) + X ) + ( random() / 10 ^ (PREC-trunc(lg(Y-X))) )

数字：(X = 500，Y = 1500，PREC = 20)

( random() * (1500-500) + 500 ) + ( random() / 10 ^ (20-trunc(lg(1000))) )
( random() * 1000 + 500 ) + ( random() / 10 ^ (17) )

这有一些问题：

• 2阶段随机生成（随机数是多少？）
• 第一个随机返回 1 ->结果可能超出范围

2：通过随机数猜测精度，

您定义一些尝试（例如4）通过生成随机数来计算精度并每次计算精度：

- 0.4663164 -> PREC=7
- 0.2581916 -> PREC=7
- 0.9147385 -> PREC=7
- 0.129141  -> PREC=6 -> 7, correcting by the average of the other tries

这是我的想法。