寻找5字节PRNG的种子
一个古老的想法，但从那时起，我无法绕过寻找一些合理的方法来解决它引发的问题。 所以我“发明了”（见下文）一个非常紧凑的，在我看来，PRNG表现相当好，但我无法弄清算法在大比特深度为它构建合适的种子值。 我目前的解决方案很简单，它的运行时间是O（n ^ 3）。
发电机
我的想法来自用于声音生成的一些旧的8位机器的异或龙头（本质上是LFSR）。 我将XOR作为C64的基础，尝试将操作码组合在一起，并体验结果。 最终的工作解决方案如下所示：
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代码更长，即使使用无符号整数的全部深度，C也没有必要的进位逻辑来将高位移位到加法操作。
有关性能分析和比较，请参阅下面的问题。
问题/问题
生成器的核心问题是找到合适的num1和num2，这将使它遍历给定位深度的整个可能序列。 在本节的最后，我附上了我的代码，它只是蛮力的。 它可以在合理的时间内完成多达12位，你可以等待所有16位（顺便说一下，有5736对可能的对），你可能会得到几个20位如果你有耐心。 但O（n ^ 3）真的很讨厌......
（谁将会找到第一个完整的32位序列？）
其他有趣的问题：
对于num1和num2，只有奇数值才能产生完整的序列。 为什么？ 这可能并不难（简单的逻辑，我猜），但我从来没有合理证明。
沿着num1（add值）有一个镜像属性，即如果给定'b'num2的'a'给出了一个完整的序列，那么'a'（在给定位深度）的2补码具有相同的num2也是一个完整的序列。 我只用我计算的所有世代来观察这种情况。
第三个有趣的特性是，对于所有的num1和num2对，结果序列似乎形成正确的圆圈，也就是说，至少数字零似乎总是圈的一部分。 没有这个属性，我的蛮力搜索就会死在一个无限循环中。
奖金：这个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): %08Xn", 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（add），Y轴是num2（xor），点越亮，序列越长。 其他位深度在模式上看起来非常相似：它们似乎都被分成了16个主要的瓦片，其中两个图案以镜像重复。 瓦片的相似性并不完整，例如从左上角到右下角的对角线清晰可见，而其相反则不存在，但对于全长序列，该属性似乎是可靠的。
依靠这个，甚至可以比以前的假设减少工作量，但仍然是O（n ^ 3）......
性能分析
截至目前，可能产生的最长序列是24位：在我的电脑上，需要大约5个小时才能完成24位的完整序列。 对Diehard等真正的PRNG测试来说，这仍然是如此，所以到目前为止，我宁愿采用自己的方法。
首先了解发生器的作用很重要。 这决不是一个非常好的发生器，因为它很简单，它的目标就是生产出体面的数字。 在这个不需要乘法/除法操作的区域，Galois LFSR可以产生类似的性能。 所以，如果我的发生器能够超越这个发生器，它是有用的。
我进行的测试都是16位发生器。 我选择了这个深度，因为它提供了一个有用的序列长度，而数字仍然可以在两个8位部分中分解，从而可以为视觉分析呈现各种精确的图形。
测试的核心是寻找以前和当前生成的数字之间的相关性。 为此，我使用了X：Y图，其中前一代是Y，现在是X，两个图都分解为如上所述的两个图的低/高部分。 我创建了一个能够实时绘制这些图形的程序，以便能够粗略地检查数字之间的相互关系以及图形如何填满。 显然，只有最终结果显示为发电机在完整的2 ^ 16或2 ^ 16-1（伽罗瓦）周期中运行。
领域的解释：
图像由8x2 256x256图形组成，总图像尺寸为2048x512（以原始尺寸检查它们）。
左上图只是确认了一个完整的序列被绘制出来，它仅仅是一个X = r % 256; Y = r / 256; X = r % 256; Y = r / 256; 情节。
左下方的图表显示每个第二个数字只与顶部相同，只是确认数字是随机发生的。
从第二张图开始，第一行是高字节相关图。 第一个使用前一代，下一个跳过一个数字（因此使用第二代），依此类推，直到第七代。
从第二行开始，底行是低字节相关图，组织方式与上面相同。
伽罗瓦发生器，0xB400水龙头组
这是维基百科伽罗瓦例子中的发生器。 它的表现并不是最糟糕的，但它绝对不是很好。
伽罗瓦发生器，0xA55A分接头组
我找到了一个体面的伽罗瓦“种子”。 请注意，16位数的低部分看起来比上面好很多，但是我找不到任何Galois“种子”，这会使高字节模糊不清。
我的发生器，0x7F25（adc），0x00DB（eor）种子
这是我的生成器中EOR值的高字节为零的最好的。 限制高字节在8位机器上是有用的，因为如果随机性能的损失是可以承受的，那么对于较小的代码和较快的执行可以省略该计算。
我的发生器，0x778B（adc），0x4A8B（eor）种子
这是我测量的优质种子之一。
为了寻找具有良好相关性的种子，我建立了一个小程序，可以在一定程度上对它们进行分析，对伽罗瓦和我来说也是一样。 该程序确定了“高质量”的例子，然后我测试了其中的几个并从中选择了一个。
一些结论：
伽罗瓦发电机似乎比我的刚性更强。 在所有的相关图上，确定的几何图案是可观察的（一些种子产生“棋盘”图案，这里未示出），即使它不是由线组成。 我的发生器也显示模式，但随着更多的世代，他们的发展不太明确。
Galois发生器结果的一部分（包括高字节中的位）似乎本质上是刚性的，而我的发生器似乎没有这个属性。 这是一个很弱的假设，但可能需要更多的研究（以查看Galois发生器是否如此，而不是其他位组合）。
伽罗瓦发生器不存在零点（最大周期为2 ^ 16-1）。
到目前为止，我无法为20位以上的发生器生成一组好的种子。
后来我可能会更深入地寻求用Diehard测试发电机，但是到目前为止，缺乏产生足够大的种子的能力使其不可能实现。
这是某种形式的非线性移位反馈寄存器。 我不知道它是否已经被使用，但它有点像线性移位反馈寄存器。 阅读本维基百科页面，作为LSFR的介绍。 它们经常用于伪随机数生成。
然而，你的伪随机数发生器本质上是坏的，因为先前生成的数字的最高位与下一个生成的数的最低位之间存在线性相关性。 您将最高位B移出，然后新数的最低位将为XOR或B，即加法常数num1的最低位和异或常数num2的最低位，因为二进制加法是等效的排他或最低位。 您的PRNG很可能有其他类似的缺陷。 创造良好的PRNG很难。
但是，我必须承认C64代码非常紧凑！
链接地址: http://www.djcxy.com/p/37269.html