17

首先，是否存在诸如随机访问随机数生成器之类的东西，假设 rand100() 始终生成 0-100 之间的值，您不仅可以像我们习惯的那样顺序生成随机数：

for (int i=0;i<5;i++)
   print rand100()

output: 
14
75
36
22
67

但也随机访问任何随机值，如：

只要您不更改种子，rand100(0) 就会输出 14

rand100(3) 总是输出 22

rand100(4) 总是输出 67

等等...

我实际上已经找到了一个开源的生成器算法，但是你不能改变种子。我知道伪随机性是一个复杂的领域；我不知道如何更改它以添加该功能。

是否有可播种的随机访问随机数生成器，最好是开源的？或者有更好的术语吗？我可以用谷歌搜索更多信息？

如果没有，我的问题的第 2 部分将是，是否有任何可靠的随机开源传统可种子伪随机数生成器，以便我可以将其移植到多个平台/语言，同时为任何给定种子的每个平台保留一致的值序列？

4

8 回答 8

7

我没有听说过这样的事情，但在我看来，你可以使用一个像样的散列并编写一个包装函数，它接受一个种子值和你的“索引”，并通过散列函数运行它们。我不确定各种加密哈希函数输出的位的随机性，但我想有人已经看过了。

于 2010-06-10T23:19:57.247 回答
5

Blum Blum Shub是一个伪随机数生成器，带有种子和随机访问它生成的任何值。

于 2013-10-22T02:39:13.470 回答
5

PCG 系列的伪随机数生成器可以在对数时间内向前和向后跳转（即向前跳转 1000 个数字需要 O(log(1000)) 操作），这可能足以被视为随机访问。参考 C 和 C++ 实现都支持此功能。

PCG 网站首页上的表格表明许多其他生成器可以支持跳转，但我没有在任何实现中看到它。

于 2016-07-21T05:10:16.213 回答
3

有一次我读到一个曾经在谷歌工作的人写的一篇非常好的博客文章，它回答了一个与你非常相似的问题。

简而言之，答案是使用带有随机数的分组密码作为加密密钥，并将序列中您想要的数字的索引作为要加密的数据。他提到了一种可以在任何大小（以位为单位）的块上工作的密码，这很方便——我必须搜索博客才能找到密码的名称。

例如：假设您想要从 0 到 (2^32)-1 的整数随机改组。您可以使用需要 4 个字节输入并返回 4 个加密字节的分组密码来实现这一点。要遍历系列，首先“加密”一个值为 0 的块，然后是 1，然后是 2，依此类推。如果您只想要打乱序列中的第 100 万个项目，则只需加密数字 1,000,000。

使用密码获得的“随机序列”与使用散列函数获得的不同（如@MichaelBurr 建议的那样）。使用密码，您可以获得一系列整数的随机排列，并在恒定时间内对该排列中的任何项目进行采样。换句话说，“随机数”不会重复。如果使用散列函数，序列中的数字可能会重复。

说了这么多，@MichaelBurr 的解决方案更适合您的情况，我建议您使用它。

于 2012-08-05T13:25:17.347 回答
3

感谢所有回复，也感谢任何可能在此问题上提出类似问题的人，我找到了一个不完全符合我要求的解决方案，但符合我的目的。

这是一个perlin 噪声类，可以在这里找到。我不确定这相对于传统的随机数生成器在计算上有多复杂，这是一个问题，因为计划中的平台之一是 Android。此外，柏林噪声与伪随机性不同，但据我所知，高倍频程和/或频率值应该为非加密目的提供合适的随机性，其中真正随机性的统计水平并不那么重要只是随机性的表象。

该解决方案允许播种，还允许从任意点对随机集进行采样，即随机访问随机性。

这是左列用于比较的常规 c++ 随机性 (rand%200) 的示例集，以及右侧的 perlin 噪声（相当于 %200）：

91 , 100
48 , 97
5 , 90
93 , 76
197 , 100
97 , 114
132 , 46
190 , 67
118 , 103
78 , 96
143 , 110
187 , 108
139 , 79
69 , 58
156 , 81
123 , 128
84 , 98
15 , 105
178 , 117
10 , 82
13 , 110
182 , 56
10 , 96
144 , 64
133 , 105

两者都被播种为 0

柏林噪声的参数是

octaves = 8
amplitude = 100 
frequency = 9999
width/height = 10000,100

柏林噪声的顺序采样顺序很简单

for (int i=0;i<24;i++)
    floor(Get(i,i)+100);
//amplitude 100 generates noise between -100 and 100, 
//so adding 100 generates between 0 and 200
于 2010-06-11T01:04:09.237 回答
1

实现这一点的一种方法是从较小的集合中合成大量的随机数据。一种方法是使用三个预先生成的随机数据数组。每个数组应该有素数的整数。

为了产生我们的随机数，我们想象这些一次性填充中的每一个都被无限循环并增量采样；我们使用 xor 组合每个数据中的数据。

#define PRIME1 7001
#define PRIME2 7013
#define PRIME3 7019

static int pad1[PRIME1];
static int pad2[PRIME2];
static int pad3[PRIME3];

static void random_no_init (void)
{
  static int initialized = 0;
  int i;
  if (initialized)
    return;
  for (i = 0; i < PRIME1; i++) pad1[i] = random ();
  for (i = 0; i < PRIME2; i++) pad2[i] = random ();
  for (i = 0; i < PRIME3; i++) pad3[i] = random ();

  initialized = 1;
}

int random_no (int no)
{
   random_no_init ();
   return pad1[no % PRIME1] ^ pad2[no % PRIME2] ^ pad3[no % PRIME3];
}

上面的代码示例显示了一个简单的示例，它产生 344618953247 个随机可访问的整体。为确保运行之间的结果可重现，您应该提供带有种子的随机数生成器。可以在http://git.gnome.org/browse/gegl/tree/gegl/gegl-random.c找到基于相同原理构建的更复杂的系统，该系统具有基于挑选不同素数的种子变异

于 2012-12-20T03:07:37.300 回答
0

我知道的所有生成器都是迭代的。因此，任何“随机访问”都将涉及计算从第一个值到您要求的值的所有值。

最接近的方法是获取一个固定的种子，对其进行散列，然后对索引值进行散列，使用真正热情混合的东西。

或者生成一长串并存储它。

于 2010-06-10T23:25:11.103 回答
0

看看这个专利：Random-access psuedo random number generator https://patents.google.com/patent/US4791594

它使用多级比特扰码方案来生成能够随机访问的伪数序列。

这个想法是使用输入地址作为控制位来加扰多个种子数，然后对结果进行异或运算以产生输出，然后使用前一次生成的结果进行第二次加扰。

于 2018-03-29T15:26:56.603 回答