什么是好的、快速的PRNG（非加密安全）

Question

我正在寻找一个快速的 PRNG，以便我可以快速为对象创建（半）唯一的 ID。唯一性更多的是管理问题，ID 重复只是极少数情况下的问题。

它必须尽可能快，因为性能至关重要，而且是非顺序的（如果 ID 是顺序的，则管理端更有可能发生错误）。另外，我想避免较低的数字，但这可以通过重试直到检索到足够高的数字来轻松缓解。

编辑 我还应该补充一点，我要求 ID 为 32 位，因此 GUID 不起作用，需要与平台无关（目前在 PC 上实现，但也需要在 Nintendo DS、PSP、PS3、Wii、Xbox 和其他平台上工作）平台）。此外，它可能每秒被调用数千次，因此，基于输入的随机数生成是不可行的。

谢谢

Answer 1

GUID？ 许多环境都支持生成这些。

Answer 2

我不确定我的理解是否正确，但如果您使用的是 Linux 机器，则可以从 /dev/urandom 读取以获得高质量随机数流。这些数字可用于生成您需要的任何长度的字符串。 请记住，要使此解决方案发挥作用，机器应该接收来自用户（键盘/鼠标）的输入。

Answer 3

PRNG 的最佳算法是您的编程语言已经提供的任何库。它将有一个经过充分测试的算法，并且可能会聪明地使用计算机中现有的随机源，例如 /dev/random。

如果你想要“低数字”，不要只是重试，直到得到一个；这将需要永远。只需取随机数并根据您的上限对其进行修改即可。即：

random() % 1000000

返回 0 到 999,999 之间的随机数。

Answer 4

如果你真的只需要非顺序部分，那么

X[i] = (X[i-1] + a) mod b

有什么问题吗？如果 a 和 b 互质，则这将在周期 b 中重复。这使得 b=2^32 成为一个简单的选择，而 a 可以是任何大于 2 的素数。性能将以 MHz 为单位，而不是 KHz。

避免较低的数字也很简单：使用序列

X[i] = offset + (X[i-1] - offset + a) mod b

？

Answer 5

您可以使用大素数来迭代一系列大跳跃。在周期重新开始之前不会发生碰撞，而且速度非常快。

Answer 6

这可能有用：

自纪元以来的当前时间、线程 ID 和序列号的总和。

Answer 7

参见：http://www.number.com.pt/index.html

Answer 8

Fishman 和 Moore 写了一篇关于线性同余 PRNG 的论文 (

A(x) = A(x-1)|m

)。 Stackoverflow 上的这篇文章 讨论了这个算法。 如果您的平台都可以支持用于中间结果的 64 位累加器（所有现代 C 编译器都应支持 64 位

long long

变量），那么这很简单且快速，周期为 2^30，M = 2^31- 1. 上面链接的帖子有一些来自 Fishman 和 Moore 论文的 A 值。

Answer 9

尝试这个。由乔治·马尔萨利亚提供。

无法与每秒 20 亿个随机数争论。

Answer 10

如果问题是某些对象或线程生成与其他对象或线程相同的 id，请考虑用 10k 保留子 id 来填充这些 id。

如果您从前一个 id 生成随机 id，这将是同样的问题，因为 prng 是确定性的。即 id 25653 接下来总是会生成 id 7567832。总是。

您可能会考虑仅使用 prng 进行非标准 id 生成，例如生成 id 的对象。比如观察这些冲突在什么条件下发生，并使用 prng 修复这些情况。其余的可能可以安全地按顺序进行。