是否存在可随机访问的伪随机数生成器之类的东西？（最好是开源的）

发布于 2024-09-05 14:18:53 字数 533 浏览 15 评论 0原文

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

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

output: 
14
75
36
22
67

而且还可以随机访问任何随机值，例如：

rand100(0) 只要你不改变种子

rand100(3) 就会输出 14 总是输出 22

rand100(4) 总是会输出 67

等等...

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

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

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

原文

first off, is there a such thing as a random access random number generator, where you could not only sequentially generate random numbers as we're all used to, assuming rand100() always generates a value from 0-100:

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

output: 
14
75
36
22
67

but also randomly access any random value like:

rand100(0)
would output 14 as long as you didn't change the seed

rand100(3)
would always output 22

rand100(4)
would always output 67

and so on...

I've actually found an open-source generator algorithm that does this, but you cannot change the seed. I know that pseudorandomness is a complex field; I wouldn't know how to alter it to add that functionality.

Is there a seedable random access random number generator, preferably open source? or is there a better term for this I can google for more information?

if not, part 2 of my question would be, is there any reliably random open source conventional seedable pseudorandom number generator so I could port it to multiple platforms/languages while retaining a consistent sequence of values for each platform for any given seed?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

帝王念 2024-09-12 14:18:53

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

回复收藏 0 原文

不交电费瞎发啥光 2024-09-12 14:18:53

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

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

回复收藏 0 原文

筱武穆 2024-09-12 14:18:53

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

回复收藏 0 原文

葬﹪忆之殇 2024-09-12 14:18:53

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

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

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

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

话虽如此，@MichaelBurr 的解决方案更适合您的情况，我建议您使用它。

回复收藏 0 原文

请远离我 2024-09-12 14:18:53

谢谢大家的回复，
而且，对于任何可能碰巧提出类似问题的人，我找到了一个不完全是我所要求的解决方案，但符合我的目的。

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

该解决方案允许播种，并且还允许从任意点对随机集进行采样，换句话说，随机访问随机性。

下面是左列中用于比较的常规 C++ 随机性 (rand%200) 示例集，右列是柏林噪声（相当于 %200）：

两者的种子都为 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

Thanks for all the replies,
and also, for anyone who might happen upon this asking a similar question, I found a solution that isn't exactly what I asked for, but fits the bill for my purposes.

It is a perlin noise class that can be found here.
I'm not sure how computationally complex this is relative to a conventional random number generator, which is a concern, since one of the planned platforms is Android. Also, perlin noise isn't the same thing as pseudorandomness, but from what I can tell, a high octave and/or frequency value should provide suitable randomness for non-cryptographic purposes, where the statistical level of true randomness isn't as important as the mere appearance of randomness.

This solution allows seeding, and also allows sampling a random set from any point, in other words, random access randomness.

here's an example set of regular c++ randomness (rand%200) on the left column for comparison, and perlin noise (with the equivalent of %200) on the right:

both were seeded to 0

the parameters for the perlin noise were

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

the sequential sampling order for the perlin noise was simply

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

回复收藏 0 原文

失去的东西太少 2024-09-12 14:18:53

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

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

#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

One way of achieving this is to synthesize a larger amount of random data from a smaller set. One way of doing this is to have three arrays of pre-generated random data. Each array should have prime number of entires.

To produce our random numbers we imagine each of these one-time pads to be looped inifintely and sampled incrementally; we combine the data in each of them using 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];
}

The code sample above shows a simple example that yields 344618953247 randomly accessible entires. To ensure reproducible results between runs, you should provide a random number generator with a seed. A more complex system built on the same principle with seed variation based on picking different primes can be found at http://git.gnome.org/browse/gegl/tree/gegl/gegl-random.c

回复收藏 0 原文