Clo*_*oud 7 c random algorithm statistics
我正在玩我在其他SO帖子(在下面的参考文献中列出)中找到的一对算法,并且我试图找出如何改进分发.我通过将位数加倍来有效地扩展随机数的范围,并且希望确保分布尽可能均匀,同时消除(或至少减少)模偏差和其他伪像对混洗算法的影响这将使用我修改的随机数生成器的结果.
所以,这是我的理解是,如果我初始化我RNG以恒定的种子(即:srand(1))我将与调用得到确定性的输出相同的模式rand()在一个for循环.现在,如果我要初始化我的种子srand(time(NULL)),它将是一个不同的模式,但它仍然可能无法解决以下问题:我试图弄清楚我是否要实现以下算法:
我能够:
a,b ? Z+ on [0, RAND_MAX](a并且b是零和RAND_MAX包含之间的正整数).虽然输出rand()应该是均匀分布的,但我不知道是否保证给出N次,N + 1次调用rand每个循环的值,并在随机序列重复之前给出每一对在点(1)中的列表本身又来了.我的新随机数生成器理论上可以生成随机值[0, RAND_MAX ^ 2],但我不知道在这个范围内是否有可能永远不会由我的算法生成的"漏洞".
我试图自己进一步研究这个问题,但是我无法找到有关rand()C中产生的随机序列持续多长时间的信息,直到它重复出现为止.缺乏这些和其他信息,我无法弄清楚是否有可能生成每一对(a,b).
那么,使用rand(),是否有可能实现第(1)点,如果是的话,是否有任何关于如何根据第(2)点优化其"随机性"的可靠建议？
感谢您的时间和帮助.
我后来重新讨论了这个问题并使用8位PRNG进行了模拟.虽然它确实可以生成所有可能的坐标对,但实际上分布非常有趣,并且绝对不均匀.最后,我阅读了几篇有关PRNG的文章/论文,并使用Mersenne Twiser算法生成所需的额外位(即MT19937-64).
参考
<https://stackoverflow.com/questions/9775313/extend-rand-max-range> <https://stackoverflow.com/questions/6127503/shuffle-array-in-c> 正如评论中指出的， 的行为rand()取决于实现。因此，让我们做一些简化的假设来解决问题：
rand()可以生成从0到 的所有值RAND_MAX。理由：如果不能，那么生成所有可能的对（a，b）会更加困难。rand()生成统计随机序列。理由：组合两个随机函数（或相同的一个随机函数两次）的结果仅与基本随机函数一样好。当然，我们不应该期望结果比构建块更好，因此实现中的任何缺陷rand()都会反映在由它组成的任何函数中。
播种rand()为给定种子生成确定性序列，因为种子决定了 PRNG 的初始状态。序列的最大周期为 2 N，其中N是状态中的位数。请注意，状态实际上可能具有比 多的位RAND_MAX，对于本节我们假设RAND_MAX= (2 N - 1) 。因为它是一个序列，所以生成两个连续的“随机” N位值 a 和 b 意味着a \xe2\x89\xa0 b。因此，方法a *( RAND_MAX+ 1)+ b会有一些漏洞。
关于\xe2\x89\xa0 b的一点解释：PRNG通过维护N位的内部状态来工作。它唯一地使用该状态来确定其下一个状态，因此一旦相同的状态重复出现，序列就会开始重复。序列开始重复之前经历的状态数称为周期。因此，从技术上讲，我们可以有a = b，但这意味着周期为 1，这是一个非常糟糕的 PRNG。有关更多信息，有关 PRNG 周期的有用答案已发布在软件工程网站上。
\n允许连续“随机”调用相等的一种方式是生成2 N位数字，但仅考虑一定数量的有效位，即丢弃一些位。现在，我们可以得到a = b，尽管概率比另一个随机数c稍低。请注意，这与Java 随机数生成器的工作原理类似。它使用 48 位进行播种，但输出 32 位随机数，丢弃 16 位（假设种子中的位数 = 状态中的位数）。
\n但是，由于您需要的值大于RAND_MAX，因此您可以使用上述方法，然后连接这些位，直到获得足够的位来达到所需的最大值（尽管同样，分布不太均匀）。