如何从随机布尔生成器制作均匀的随机整数生成器?

我有一个基于硬件的布尔生成器,可以统一生成1或0。如何使用它制作统一的8位整数生成器?我目前正在使用收集的布尔值为8位整数创建二进制字符串。生成的整数不是均匀分布的。它遵循this page中解释的分布。具有相同数量的1和0的整数,例如85(01010101)和-86(10101010),具有最高的机会被生成,并以0的整数(00)生成整数(00) (11111111)的机率最低。

这是我为每个可能的4位整数注释的页面。我们可以看到它们不是统一的。具有相同的1和0数目的3、5、6,-7,-6和-4具有⁶/₁₆概率,而其所有位都相同的0和-1仅具有only /₁₆概率。 / p>

如何从随机布尔生成器制作均匀的随机整数生成器?

这是my implementation on Kotlin

lcxs123 回答:如何从随机布尔生成器制作均匀的随机整数生成器?

根据您的编辑,此处似乎存在误解。通过“统一的4位整数”,您似乎要牢记以下几点:

  1. 从0开始。
  2. 生成一个随机位。如果为1,则加1,否则减去1。
  3. 将步骤2重复三遍。
  4. 输出结果号码。

尽管随机位生成器可能会生成一些位,其中每个结果都可能与其他结果一样随机生成,并且每个4位块可能与其他任何结果都将随机生成一样,但每个位中的位数块不是均匀分布的。

您想要什么整数范围?假设您要生成4位整数。您是否想要[-4,4]的范围,如您问题中的4位随机游走,还是想要[-8,7]的范围,当您处理4-时得到的是位块是二进制补码整数?

如果是前者,则随机游走不会生成均匀分布,因此您需要以其他方式解决问题。

在这种情况下,要生成[-4,4]范围内的统一随机数,请执行以下操作:

  1. 取4位随机位发生器,并在[0,15)中将它们视为整数;
  2. 如果整数大于8,请转到步骤1。
  3. 从整数中减去4并将其输出。

此算法使用拒绝采样,但是它是可变时间的(因此,只要可以在安全攻击中利用时间差,就不合适了)。同样会生成其他范围内的数字,但是细节太复杂,无法在此答案中进行描述。有关详细信息,请参见我在random number generation methods上的文章。


根据您显示的代码,构建byteintlong的方法很容易出错。例如,构建8位字节以实现所需内容的更好方法如下(请记住,我对Kotlin不太熟悉,因此语法可能是错误的):

val i = 0
val b = 0
for (i = 0; i < 8; i++) {
   b = b << 1; // Shift old bits
   if (bitStringBuilder[i] == '1') {
      b = b | 1; // Set new bit
   } else {
      b = b | 0; // Don't set new bit
   }
}
value = (b as byte) as T

此外,如果MediatorLiveData不是线程安全的,那么您使用StringBuilder收集位的方法也不是(特别是因为StringBuilder不是线程安全的)。


您建议的方法将布尔生成器的八位组合为一个统一整数,从理论上讲是可行的。但是,实际上有几个问题:

  • 您没有提到它是哪种硬件。在大多数情况下,除非硬件是为此目的而设计的所谓的“真正随机数生成器”,否则硬件不太可能生成统一的随机布尔位。例如,硬件可能会生成均匀分布的位,但具有周期性的行为。
  • 表示与理想的随机值相比,预测生成器生成的值有多困难。例如,具有32位熵的64位数据块与理想的随机32位数据块一样难以预测。表征硬件设备的熵(或产生不可预测值的能力)绝非易事。除其他外,这涉及熵测试,必须在适合硬件的整个操作条件范围内(例如温度,电压)进行熵测试。
  • 大多数硬件无法产生统一的随机值,因此通常需要执行一个额外的步骤,称为随机抽取熵抽取无偏美白去偏斜可以将硬件生成的值转换为均匀分布的随机数。但是,如果首先表征硬件的熵,则效果最好(请参见上一点)。
  • 最后,您仍然必须测试整个过程是否提供了出于您的目的“足够随机”的数字。有几种统计测试试图做到这一点,例如NIST的统计测试套件或TestU01。

有关更多信息,请参见“ Nondeterministic Sources and Seed Generation”。


在编辑此页面后,看来您正在以错误的方式处理该问题。要产生统一的随机数,您不必添加均匀分布的随机位(例如bit() + bit() + bit()),而是连接它们(例如{{1} }。但是,由于我上面提到的原因,这再次在理论上有效,但在实践中无效。

本文链接:https://www.f2er.com/3110700.html

大家都在问