带有前后支持的随机数生成？

Question

带有前后支持的随机数生成？

3

如何编写两个函数生成支持下一个和上一个随机数的函数？

我的意思是如何编写两个函数：next_number()和previous_number()，其中next_number()函数生成一个新的随机数，而previous_number()函数生成先前生成的随机数。

例如：

int next_number()
{
   // ...?
}

int previous_number()
{
   // ...?
}

int num;

// Forward random number generating.
// ---> 54, 86, 32, 46, 17
num = next_number(); // num = 54
num = next_number(); // num = 86
num = next_number(); // num = 32
num = next_number(); // num = 46
num = next_number(); // num = 17

// Backward random number generating.
// <--- 17, 46, 32, 86, 54
num = previous_number(); // num = 46
num = previous_number(); // num = 32
num = previous_number(); // num = 86
num = previous_number(); // num = 54

- Amir Saniyan

1

你不能把到目前为止生成的所有数字都存储在一个列表中吗？ - mclaassen

1

如果您只需要一个有限的N个数字序列，则随机洗牌整数1..N，并存储洗牌后的集合。 - mbeckish

在你的例子中，如果你第五次调用 previous_number() 会发生什么？ - mbeckish

@mbeckish：一个新的随机数 :) - Amir Saniyan

1

我认为你需要定义一下，“随机”对你而言是什么意思。是指“不连续”，还是指“尽可能少的确定性”（如 http://en.wikipedia.org/wiki/Random_number_generation）？ - Erki Aring

5个回答

阿里云服务器只需要99元/年，新老用户同享，点击查看详情

3

一些线性同余生成器（常见但不是很好的伪随机数生成器）是可逆的。

它们通过next = (a * previous + c) mod m工作。如果a在模m下有模乘逆元，那么这就是可逆的。通常情况下，这种情况经常发生，因为m通常是2的幂次方，而且a通常是奇数。

例如，对于第一个链接中表格中的“MSVC”参数：

m = 2³²
a = 214013
c = 2531011

反转是：

previous = (current - 2531011) * 0xb9b33155;

使用模2³²的类型使其正常工作。

- harold

2

假设您有一个由以下公式定义的线性同余序列S:

S[0] = seed
S[i] = (p * S[i-1] + k) % m

对于一些满足gcd(p, m) == 1的p、m和k，则可以找到一个q，使得(p * q) % m == 1，然后计算：

S[i-1] = (q * (S[i] - k)) % m

换句话说，如果您选择适当的p并预先计算q，则可以以O(1)时间顺序遍历您的序列。

- candu

2

生成可索引的伪随机序列的一种相对简单的方法是选择某个（较好的）加密算法和一个固定的加密密钥，然后定义：

sequence(i): encrypt(i, known_key)

你不需要知道i的值，因为你可以从数字中解密它：

next(r): encrypt(decrypt(r, known_key) + 1)

prev(r): encrypt(decrypt(r, known_key) - 1)

因此，i 不必是一个小整数；由于你需要做的唯一算术运算是加上或减去一个小整数，因此 Bignum 实现非常简单。因此，如果您想要 128 位伪随机数，您可以将第一个 i 设置为从 /dev/random 中提取的 128 位随机数。

您必须在静态存储中保留整个 i 的值，伪随机数的周期不能大于 i 的范围。虽然对于这个问题的任何解决方案都是如此：由于 next() 和 prev() 运算符必须是函数，每个值都有一个唯一的后继和前驱，因此在值循环中只能出现一次。这与 Mersenne twister 完全不同，例如其周期远大于 2³²。

- rici

0

我认为你所要求的是一个确定性随机数生成器。这是没有意义的，因为如果它是确定性的，那么它就不是随机的。唯一的解决方案是生成一个随机数列表，然后在这个列表中前后移动。

PS！我知道所有软件PRNG本质上都是确定性的。当然，你可以使用它来创建所需的功能，但不要自欺欺人，这与随机性无关。如果你的软件设计需要具有确定性PRNG，那么你可能可以完全跳过PRNG部分。

- Erki Aring

所有的伪随机数生成器都是确定性的。OP正在寻求一个其逆序列也是确定性的伪随机序列，这将限制其循环周期为可能的随机值数量。 - rici

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，

- that other guy · Accepted Answer

你可以使用伪随机函数（PRF）轻松实现此操作。这些函数需要一个密钥和一个值，并基于它们输出一个伪随机数。你可以从 /dev/random 选择一个在程序运行期间保持不变的密钥，然后将一个整数馈送给函数，增加它以向前移动或减少以向后移动。以下是一个伪代码示例：

initialize():
    Key = sufficiently many bytes from /dev/random
    N = 0

next_number():
    N = N + 1
    return my_prf(Key, N)

previous_number():
    N = N - 1
    return my_prf(Key, N)

大多数密码学库中都包含强伪随机函数。正如rici所指出的，您也可以使用任何加密函数（加密函数是伪随机置换的子集，是PRF的一种，其周期非常巨大，因此差异并不重要）。