保证值序列所有可能排列的伪随机分布 - C++
pseudo random distribution which guarantees all possible permutations of value sequence - C++
随机问题。
我正在尝试创建一个程序来生成伪随机分布。我正试图找到适合我需要的伪随机算法。这些是我的担忧：
1) 我需要一个输入，每次使用它都能产生相同的输出。
2) 它需要足够随机，以至于查看输入 1 的输出的人看不出它与输入 2 的输出（等等）之间没有任何联系，但不需要加密安全或真正随机。
3)它的输出应该是一个介于 0 和 (29^3200)-1 之间的数字，该范围内的每个可能的整数都是一个可能的且同样（或接近）可能的输出。
4) 我希望能够保证 410 个输出序列的每个可能排列也是连续输入的潜在输出。换句话说，0 到 (29^3200)-1 之间的 410 个整数的所有可能分组应该是顺序输入的潜在输出。
5) 我希望函数是可逆的，这样我就可以取一个整数或一系列整数，然后说出哪个输入或哪个输入系列会产生那个结果。
到目前为止我开发的方法是运行通过一个简单的哈尔森序列输入：
boost::multiprecision::mpz_int denominator = 1;
boost::multiprecision::mpz_int numerator = 0;
while (input>0) {
denominator *=3;
numerator = numerator * 3 + (input%3);
input = input/3;
}
并将结果乘以 29^3200。它满足 1-3 的要求，但不满足 4 的要求。而且它只对单个整数是可逆的，对序列不是可逆的（因为不是所有的序列都可以由它产生）。我在 C++ 中工作，使用 boost multiprecision。
任何人都可以给我关于生成满足这些要求的随机分布的方法的任何建议，或者只是 class 值得为此研究的算法，将不胜感激。预先感谢您考虑我的问题。
----更新----
由于多个评论者关注的是所讨论数字的大小，我只是想明确表示，我认识到使用此类集合会带来实际问题，但在提出这个问题时，我只对理论感兴趣或问题的概念方法 - 例如，想象使用更小的整数集，如 0 到 99，以及 10 个输出序列集的排列。你将如何设计一个算法来满足这五个条件 - 1）输入是确定的，2）随机出现（至少对人眼而言），3）范围内的每个整数都是可能的输出，4）不仅是所有值，而且值序列的所有排列都是可能的输出，5）函数是可逆的。
---第二次更新---
非常感谢@Severin Pappadeux，我能够反转 lcg。我想我会补充一点我所做的，希望能让任何人在未来更容易看到这一点。首先，这些是反模函数的优秀资源：
https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-inverses
https://www.khanacademy.org/computer-programming/discrete-reciprocal-mod-m/6253215254052864
如果你采用等式 next=ax+c%m，使用以下代码和你的 a 和 m 值将打印出你需要求逆的欧几里得方程，以及逆的值：
int qarray[12];
qarray[0]=0;
qarray[1]=1;
int i =2;
int reset = m;
while (m % a >0) {
int remainder=m%a;
int quotient=m/a;
std::cout << m << " = " << quotient << "*" << a << " + " << remainder << "\n";
qarray[i] =qarray[i-2]-(qarray[i-1]*quotient);
m=a;
a=remainder;
i++;
}
if (qarray[i-1]<0) {qarray[i-1]+=reset;}
std::cout << qarray[i-1] << "\n";
我花了一段时间才弄清楚的另一件事是，如果你得到一个否定的结果，你应该加上 m。您应该在新等式中添加一个类似的项：
prev = (ainverse(next-c))%m;
if (prev<0) {prev+=m;}
我希望能对未来走这条路的人有所帮助。
好的，我不确定是否有一般性答案，所以我会专注于具有 64 位内部 state/seed、产生 64 位输出并具有 2^64-1 周期的随机数生成器.特别是，我会以
的形式查看线性同余生成器（又名 LCG）
next = (a * prev + c) mod m
其中 a 和 m 互为质数
所以：
1) 检查
2) 检查
3) 检查（好吧，当然是 64 位 space）
4) 检查（再次，我相信除了 0，但是 64 位的每一个排列都是从一些种子开始的 LCG 的输出）
5) 检查。众所周知，LCG 是可逆的，即可以
prev = (next - c) * a_inv mod m
其中 a_inv 可以使用 Euclid 算法从 a、m 计算得出
好吧，如果你觉得没问题，你可以尝试在你的 15546 位中实现 LCG space
更新
快速搜索显示双面 LCG discussion/code 此处
Reversible pseudo-random sequence generator
在您的更新中，"appears random (to the human eye)" 是您使用的措辞。 "appears random" 的定义不是一个公认的话题。 "randomness."
有不同程度的测试
但是，如果您只是想让它在人眼看来是随机的，您可以只使用环乘法。
- 从生成N的想法开始！ 0 到 M 之间的值（N>=410，M>=29^3200）
- 将这些组合成一个大数字。我们将生成一个范围从 0 到 *M^N! 的数字。如果我们能证明伪随机数生成器生成从 0 到 M^N 的每个值！，我们保证您的排列规则。
- 现在我们需要实现"appear random."对于人眼来说，线性全等生成器就足够了。挑一个周期大于等于410!*M^N满足the rules的LCG，保证周期完整。确保公平的最简单方法是选择 x' = (ax+c) mod M^N!
形式的 LCG
这样就可以了。现在，困难的部分是证明你所做的事情值得你花时间。考虑一下 29^3200 长序列的周期超出了物理现实的范围。你永远不会真正使用它。曾经。考虑由约瑟芬结制成的超导体（10^-12kg 处理 10^11bits/s）称整个宇宙的质量为 3*10^52kg）可以处理大约 10^75bits/s。一个可以数到 29^3200 的数字大约有 15545 位长，因此超级计算机可以处理大约 6.5x10^71 numbers/s。这意味着大约需要 10^4600 秒才能算出那么高，或者大约 10^4592 年。大约 10^12 年后的某个时候，预计星星会永久地熄灭，所以可能需要一段时间。
0 和 M-1 之间有 M**N 个 N 个数字序列。
您可以想象以（伪随机）序列一个接一个地写入所有这些，并将您的读取指针随机放置在 0 和 M-1 之间的 N*(M**N) 数字的结果循环中...
def output(input):
total_length = N*(M**N)
index = input % total_length
permutation_index = shuffle(index / N, M**N)
element = input % N
return (permutation_index / (N**element)) % M
当然，对于 0 和 M-1 之间的 N 个元素的每个排列，都有一个 N 个连续输入序列产生它（只需取消排列排列索引）。我还要说（仅使用对称推理）给定任何起始输入，下一个 N 元素的输出是等概率的（每个数字和 N 个数字的每个序列在总周期中均等表示）。
随机问题。
我正在尝试创建一个程序来生成伪随机分布。我正试图找到适合我需要的伪随机算法。这些是我的担忧：
1) 我需要一个输入，每次使用它都能产生相同的输出。
2) 它需要足够随机，以至于查看输入 1 的输出的人看不出它与输入 2 的输出（等等）之间没有任何联系，但不需要加密安全或真正随机。
3)它的输出应该是一个介于 0 和 (29^3200)-1 之间的数字，该范围内的每个可能的整数都是一个可能的且同样（或接近）可能的输出。
4) 我希望能够保证 410 个输出序列的每个可能排列也是连续输入的潜在输出。换句话说，0 到 (29^3200)-1 之间的 410 个整数的所有可能分组应该是顺序输入的潜在输出。
5) 我希望函数是可逆的，这样我就可以取一个整数或一系列整数，然后说出哪个输入或哪个输入系列会产生那个结果。
到目前为止我开发的方法是运行通过一个简单的哈尔森序列输入：
boost::multiprecision::mpz_int denominator = 1;
boost::multiprecision::mpz_int numerator = 0;
while (input>0) {
denominator *=3;
numerator = numerator * 3 + (input%3);
input = input/3;
}
并将结果乘以 29^3200。它满足 1-3 的要求，但不满足 4 的要求。而且它只对单个整数是可逆的，对序列不是可逆的（因为不是所有的序列都可以由它产生）。我在 C++ 中工作，使用 boost multiprecision。
任何人都可以给我关于生成满足这些要求的随机分布的方法的任何建议，或者只是 class 值得为此研究的算法，将不胜感激。预先感谢您考虑我的问题。
----更新----
由于多个评论者关注的是所讨论数字的大小，我只是想明确表示，我认识到使用此类集合会带来实际问题，但在提出这个问题时，我只对理论感兴趣或问题的概念方法 - 例如，想象使用更小的整数集，如 0 到 99，以及 10 个输出序列集的排列。你将如何设计一个算法来满足这五个条件 - 1）输入是确定的，2）随机出现（至少对人眼而言），3）范围内的每个整数都是可能的输出，4）不仅是所有值，而且值序列的所有排列都是可能的输出，5）函数是可逆的。
---第二次更新---
非常感谢@Severin Pappadeux，我能够反转 lcg。我想我会补充一点我所做的，希望能让任何人在未来更容易看到这一点。首先，这些是反模函数的优秀资源：
https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-inverses
https://www.khanacademy.org/computer-programming/discrete-reciprocal-mod-m/6253215254052864
如果你采用等式 next=ax+c%m，使用以下代码和你的 a 和 m 值将打印出你需要求逆的欧几里得方程，以及逆的值：
int qarray[12];
qarray[0]=0;
qarray[1]=1;
int i =2;
int reset = m;
while (m % a >0) {
int remainder=m%a;
int quotient=m/a;
std::cout << m << " = " << quotient << "*" << a << " + " << remainder << "\n";
qarray[i] =qarray[i-2]-(qarray[i-1]*quotient);
m=a;
a=remainder;
i++;
}
if (qarray[i-1]<0) {qarray[i-1]+=reset;}
std::cout << qarray[i-1] << "\n";
我花了一段时间才弄清楚的另一件事是，如果你得到一个否定的结果，你应该加上 m。您应该在新等式中添加一个类似的项：
prev = (ainverse(next-c))%m;
if (prev<0) {prev+=m;}
我希望能对未来走这条路的人有所帮助。
好的，我不确定是否有一般性答案，所以我会专注于具有 64 位内部 state/seed、产生 64 位输出并具有 2^64-1 周期的随机数生成器.特别是，我会以
的形式查看线性同余生成器（又名 LCG）next = (a * prev + c) mod m
其中 a 和 m 互为质数
所以：
1) 检查
2) 检查
3) 检查（好吧，当然是 64 位 space）
4) 检查（再次，我相信除了 0，但是 64 位的每一个排列都是从一些种子开始的 LCG 的输出）
5) 检查。众所周知，LCG 是可逆的，即可以
prev = (next - c) * a_inv mod m
其中 a_inv 可以使用 Euclid 算法从 a、m 计算得出
好吧，如果你觉得没问题，你可以尝试在你的 15546 位中实现 LCG space
更新
快速搜索显示双面 LCG discussion/code 此处
Reversible pseudo-random sequence generator
在您的更新中，"appears random (to the human eye)" 是您使用的措辞。 "appears random" 的定义不是一个公认的话题。 "randomness."
有不同程度的测试但是，如果您只是想让它在人眼看来是随机的，您可以只使用环乘法。
- 从生成N的想法开始！ 0 到 M 之间的值（N>=410，M>=29^3200）
- 将这些组合成一个大数字。我们将生成一个范围从 0 到 *M^N! 的数字。如果我们能证明伪随机数生成器生成从 0 到 M^N 的每个值！，我们保证您的排列规则。
- 现在我们需要实现"appear random."对于人眼来说，线性全等生成器就足够了。挑一个周期大于等于410!*M^N满足the rules的LCG，保证周期完整。确保公平的最简单方法是选择 x' = (ax+c) mod M^N! 形式的 LCG
这样就可以了。现在，困难的部分是证明你所做的事情值得你花时间。考虑一下 29^3200 长序列的周期超出了物理现实的范围。你永远不会真正使用它。曾经。考虑由约瑟芬结制成的超导体（10^-12kg 处理 10^11bits/s）称整个宇宙的质量为 3*10^52kg）可以处理大约 10^75bits/s。一个可以数到 29^3200 的数字大约有 15545 位长，因此超级计算机可以处理大约 6.5x10^71 numbers/s。这意味着大约需要 10^4600 秒才能算出那么高，或者大约 10^4592 年。大约 10^12 年后的某个时候，预计星星会永久地熄灭，所以可能需要一段时间。
0 和 M-1 之间有 M**N 个 N 个数字序列。
您可以想象以（伪随机）序列一个接一个地写入所有这些，并将您的读取指针随机放置在 0 和 M-1 之间的 N*(M**N) 数字的结果循环中...
def output(input):
total_length = N*(M**N)
index = input % total_length
permutation_index = shuffle(index / N, M**N)
element = input % N
return (permutation_index / (N**element)) % M
当然，对于 0 和 M-1 之间的 N 个元素的每个排列，都有一个 N 个连续输入序列产生它（只需取消排列排列索引）。我还要说（仅使用对称推理）给定任何起始输入，下一个 N 元素的输出是等概率的（每个数字和 N 个数字的每个序列在总周期中均等表示）。