一个古老的想法，但从那时起，我就无法找到一些相当好的方法来解决它提出的问题。所以我“发明”（见下文）一个非常紧凑的，并且在我看来，性能相当不错的 PRNG，但我无法找出算法来为它在大位深度上构建合适的种子值。我目前的解决方案只是暴力破解，它的运行时间是 O(n^3)。
发电机
我的想法来自 XOR taps（本质上是LFSRs）一些用于声音生成的旧 8 位机器。我在 C64 上摆弄 XOR 作为基础，尝试将操作码放在一起，并体验了结果。最终的工作解决方案如下所示：
asl
adc #num1
eor #num2
这是 6502 上的 5 个字节。使用精心选择的 num1 和 num2，在累加器中它以看似随机的顺序迭代所有 256 个值，也就是说，当用于填充屏幕时它看起来相当随机（我写了一点 256b那时的演示）。有 40 个合适的 num1 和 num2 对，都给出了不错的序列。
这个概念可以很好地概括，如果用纯 C 表示，它可能看起来像这样（BITS作为序列的位深度）：
r = (((r >> (BITS-1)) & 1U) + (r << 1) + num1) ^ num2;
r = r & ((1U<<BITS)-1U);
由于它是通用的，因此该 C 代码更长，即使使用无符号整数的完整深度，C 也没有必要的进位逻辑将移位的高位转移到加法操作。
对于一些性能分析和比较，请参阅下面的问题之后。
问题/问题
生成器的核心问题是找到合适的 num1 和 num2 使其迭代给定位深度的整个可能序列。在本节的最后，我附上了我的代码，它只是暴力破解它。它将在合理的时间内完成最多 12 位，您可能会等待所有 16 位（顺便说一下，有 5736 对可能的配对，前一阵子通过一夜之间的完整搜索获得），您可能会得到几个 20 位如果你有耐心。但是 O(n^3) 真的很讨厌...
（谁能找到第一个完整的 32 位序列？）
出现的其他有趣的问题：
对于 num1 和 num2 只有奇数值能够产生完整的序列。为什么？这可能并不难（我猜是简单的逻辑），但我从未合理地证明过这一点。
沿着 num1（相加值）有一个镜像属性，也就是说，如果 'a' 和给定的 'b' num2 给出一个完整的序列，那么 'a' 的 2 补码（在给定的位深度内）具有相同的num2 也是一个完整的序列。我只观察到我计算的所有完整世代都可靠地发生了这种情况。
第三个有趣的特性是，对于所有 num1 和 num2 对，得到的序列似乎形成了正确的圆圈，也就是说，至少数字 0 似乎总是圆圈的一部分。如果没有这个属性，我的蛮力搜索将陷入无限循环。
奖励：这个 PRNG 以前是否已经知道？（我只是重新发明了它）？
这是蛮力搜索的代码（C）：
#define BITS 16
#include "stdio.h"
#include "stdlib.h"
int main(void)
{
unsigned int r;
unsigned int c;
unsigned int num1;
unsigned int num2;
unsigned int mc=0U;
num1=1U; /* Only odd add values produce useful results */
do{
num2=1U; /* Only odd eor values produce useful results */
do{
r= 0U;
c=~0U;
do{
r=(((r>>(BITS-1)) & 1U)+r+r+num1)^num2;
r&=(1U<<(BITS-1)) | ((1U<<(BITS-1))-1U); /* 32bit safe */
c++;
}while (r);
if (c>=mc){
mc=c;
printf("Count-1: %08X, Num1(adc): %08X, Num2(eor): %08X\n", c, num1, num2);
}
num2+=2U;
num2&=(1U<<(BITS-1)) | ((1U<<(BITS-1))-1U);
}while(num2!=1U);
num1+=2U;
num1&=((1U<<(BITS-1))-1U); /* Do not check complements */
}while(num1!=1U);
return 0;
}
这表明它正在工作，每次迭代后将输出找到的对，如果它的序列长度等于或长于前一个。修改BITS其他深度序列的常数。
种子狩猎
我做了一些与种子有关的图表。这是一张很好的图片，显示了所有 9 位序列长度：
白点是全长序列，X 轴代表 num1（加），Y 轴代表 num2（异或），点越亮，序列越长。其他位深度在模式上看起来非常相似：它们似乎都被分解为 16 个主要图块，其中两个模式通过镜像重复。瓷砖的相似性并不完整，例如从左上角到右下角的对角线上方清晰可见，而相反的则不存在，但对于全长序列，此属性似乎是可靠的。
依靠这一点，可以比以前的假设减少更多的工作，但这仍然是 O(n^3)...
性能分析
截至目前，可能生成的最长序列是 24 位：在我的计算机上，为此暴力破解一个完整的 24 位序列大约需要 5 个小时。对于像Diehard这样的真实 PRNG 测试来说，这仍然只是马马虎虎，所以到目前为止，我宁愿采用自己的方法。
首先，了解生成器的作用很重要。这绝不会是一个非常简单的生成器，它的目标是快速生成体面的数字。在这个不需要乘法/除法运算的区域上，伽罗瓦 LFSR可以产生类似的性能。因此，如果我的生成器能够胜过这个生成器，它就可以派上用场。
我进行的测试都是 16 位生成器。我之所以选择这个深度，是因为它提供了一个有用的序列长度，而数字仍然可以分成两个 8 位部分，从而可以呈现各种位精确图以进行可视化分析。
测试的核心是寻找与先前和当前生成的数字的相关性。为此，我使用了 X:Y 绘图，其中上一代是 Y，当前是 X，两者都分解为低/高部分，如上所述的两个图表。我创建了一个能够实时绘制这些步骤的程序，这样也可以粗略地检查数字是如何相互跟随的，图表是如何填充的。显然，这里只显示最终结果，因为生成器运行了完整的 2^16 或 2^16-1 (Galois) 循环。
字段说明：
这些图像由 8x2 256x256 图形组成，使总图像尺寸为 2048x512（以原始尺寸检查它们）。
左上图只是确认确实绘制了一个完整的序列，它只是一个
X = r % 256; Y = r / 256;图。左下图显示每隔一个数字仅以与顶部相同的方式绘制，只是确认这些数字合理地随机出现。
从第二张图中，顶行是高字节相关图。他们中的第一个使用上一代，下一个跳过一个数字（所以使用上第二代），依此类推，直到上第七代。
从第二行开始，最下面一行是低字节相关图，组织方式与上面相同。
伽罗瓦发生器，0xB400 抽头组
这是在Wikipedia Galois 示例中找到的生成器。它的性能不是最差的，但它仍然绝对不是很好。
伽罗瓦发生器，0xA55A 抽头组
我发现的体面的伽罗瓦“种子”之一。请注意，16 位数字的低位部分似乎比上面的要好得多，但是我找不到任何能模糊高字节的伽罗瓦“种子”。
我的生成器，0x7F25（adc），0x00DB（eor）种子
这是我最好的生成器，其中 EOR 值的高字节为零。限制高字节在 8 位机器上很有用，因为如果可以承受随机性性能的损失，则可以省略此计算以实现更小的代码和更快的执行。
我的生成器，0x778B（adc），0x4A8B（eor）种子
根据我的测量，这是质量非常好的种子之一。
为了找到具有良好相关性的种子，我构建了一个小程序，可以在一定程度上分析它们，就像伽罗瓦和我的一样。该程序确定了“优质”示例，然后我测试了其中几个并从中选择了一个。
一些结论：
伽罗瓦生成器似乎比我的更严格。在所有相关图上，可以观察到明确的几何图案（有些种子会产生“棋盘”图案，此处未显示），即使它不是由线条组成的。我的生成器也显示了模式，但是随着代数的增加，它们的定义越来越少。
包括高字节中的位的伽罗瓦生成器结果的一部分似乎本质上是刚性的，我的生成器似乎没有该属性。这是一个薄弱的假设，但可能需要更多的研究（看看伽罗瓦生成器是否总是如此，而不是我的其他位组合）。
伽罗瓦生成器缺少零（最大周期为 2^16-1）。
到目前为止，不可能为我的生成器生成超过 20 位的一组好的种子。
稍后我可能会更深入地研究这个主题，试图用 Diehard 测试生成器，但到目前为止，由于缺乏生成足够大种子的能力，这使得它变得不可能。