4

在 [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(x-y)>1.0情况下的密度都较低。许多可能的值将被遗漏。请记住,random() 仅返回 P 个可能数字中的一个数字。然后,如果你将这个数字乘以 Q,它只会给你 P 个可能的值之一,按 Q 缩放,但你也必须将密度 P 缩放 Q。

4

9 回答 9

3

如果我很好地理解了您的问题,我将为您提供解决方案:但我会从范围中排除 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;
}
于 2011-11-05T10:40:52.573 回答
2

如果您真的想在给定范围内生成所有可能的浮点数,并且具有统一的数字密度,则需要考虑浮点格式。对于二进制指数的每个可能值,您都有不同的代码数字密度。直接生成方法需要明确地处理这个问题,而间接生成方法仍然需要考虑到它。我将开发一种直接的方法;为简单起见,以下仅指IEEE 754单精度(32 位)浮点数。

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

此外,如果您如此密切地关注结果,您将需要确保您使用的是具有足够大状态空间的良好伪随机数生成器,您可以期望它以接近均匀的概率命中每个值。这取消了 C/Unixrand()和可能的*rand48()库函数的资格;您应该改用Mersenne Twister之类的东西。


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

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

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

如果选择的子区间覆盖了由特定指数控制的整个区域,那么只需用随机位(23 位,对于 32 位 IEEE-754 浮点数)填充尾数。但是,如果子区间未覆盖整个区域,您将需要生成仅覆盖该子区间的随机尾数。

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

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

于 2011-11-07T23:04:02.257 回答
1

嗯,[0..1] * 2 == [0..2](还是统一的)

[0..1] - 0.5 == [-0.5..0.5]等等

我想知道你在哪里经历过这样的采访?

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

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

于 2011-11-05T10:42:00.510 回答
1

让我重新表述你的问题:

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

--

几个快速笔记。

  1. 这种形式的问题,正如你所说的,它是无法解决的。也就是说,如果 N = 1,我们无能为力。
  2. 我不要求它0.0是 的可能值之一random()。如果不是,那么下面的解决方案可能会在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()可能只有一位随机性。如果我然后要求您从三个值之一中进行选择,则您不能使用保证终止的函数随机地统一执行此操作。

于 2011-11-12T09:41:07.303 回答
1

考虑这种方法:

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

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

如果目标区间长度小于等于 1,则返回random()*(y-x) + x

否则,r将基础 RNG 中的每个数字映射到目标范围内的一个区间:

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

(即为每个 P 数字分配一个长度为 P 的间隔(y-x)/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)
于 2011-11-13T21:21:52.860 回答
0

在实际数学中:解决方案只是提供:

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

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

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

例如,从 0..1 获取 random() 返回值,精度为 2 位,即 0.XY,较低为 100,较高为 1100。

因此,使用上述算法,您将得到结果 0.XY * (1100-100) + 100 = XY0.0 + 100。您永远不会看到 201 作为结果,因为最后一位数字必须为 0。

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

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

在标准 IEEE 格式中具有有限的精度(即双 53 位)。因此,当您以这种方式生成一个数字时,您永远不需要生成多个额外的数字。

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

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

于 2011-11-05T11:14:27.177 回答
0

您必须考虑每次调用您的 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 中获得的最大熵。如果有必要,这可以修复。

于 2011-11-07T18:02:02.063 回答
0

当您使用 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

这就是我的想法。

于 2011-11-08T13:58:59.340 回答
0

如果我正确理解您的问题,那就是 rand() 生成间隔精细但最终离散的随机数。如果我们将它乘以很大的 (yx),这会将这些间隔精细的浮点值分散开来,从而丢失 [x,y] 范围内的许多浮点值。可以吗?

如果是这样,我认为我们已经有了 Dialecticus 已经给出的解决方案。让我解释一下为什么他是对的。

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

那么随机整数是最大的(即 w)并且我们添加到它的随机浮点数大于 z - w 以使随机数超过允许的最大值的极端情况呢?答案很简单:再次执行所有操作并检查新结果。重复直到你得到允许范围内的数字。这是一个简单的证明,即如果均匀生成的随机数超出允许范围,则该随机数会被丢弃并再次生成,从而导致在允许范围内均匀生成随机。一旦你做出这个关键的观察,你就会发现 Dialecticus 符合你的所有标准。

于 2011-11-11T03:52:49.590 回答