寻找5字节PRNG的种子
Jub*_*ian 6 random algorithm prng
一个古老的想法,但从那以后我无法找到一些合理的方法来解决它引发的问题.所以我"发明"(见下文)非常紧凑,在我看来,性能相当好的PRNG,但我无法弄清楚算法在大位深度为它构建合适的种子值.我目前的解决方案只是暴力破解,它的运行时间是O(n ^ 3).
发电机
我的想法来自XOR水龙头(基本上是LFSR)一些用于发声的老式8bit机器.我摆弄了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也没有必要的进位逻辑来将移位的高位传送到加法运算.
对于一些性能分析和比较,请在问题之后见下文.
问题/问题
生成器的核心问题是找到合适的num1和num2,这将使它迭代给定位深度的整个可能序列.在本节的最后,我附上了我的代码,这些代码只是暴力强制它.它将在合理的时间内完成多达12位,您可以等待所有16位(顺便说一下,有5736个可能的配对,前一次通过隔夜完全搜索获得),你可能会得到几个20位如果你有耐心 但O(n ^ 3)真的很讨厌......
(谁能找到第一个完整的32位序列？)
出现的其他有趣问题:
对于num1和num2,只有奇数值能够产生完整序列.为什么？这可能并不难(简单的逻辑,我猜),但我没有合理地证明它.
沿着num1(加值)有一个镜像属性,也就是说,如果给定'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): %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(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;图.左下图显示每个第二个数字仅以与顶部相同的方式绘制,只是确认数字合理地随机出现.
从第二个图中,顶行是高字节相关图.第一个使用上一代,下一个跳过一个数字(因此使用第二代),依此类推,直到第7代.
从第二行开始,底行是低字节相关图,以与上面相同的方式组织.
Galois发生器,0xB400抽头组
这是维基百科Galois示例中的生成器.它的性能并不是最糟糕的,但它仍然绝对不是很好.
Galois发生器,0xA55A抽头组
我找到了一个体面的伽罗瓦"种子".请注意,16位数的低部分似乎比上面的要好很多,但是我找不到任何可以模糊高字节的Galois"种子".
我的生成器,0x7F25(adc),0x00DB(eor)种子
这是我的生成器中最好的,其中EOR值的高字节为零.限制高字节在8位机器上很有用,因为如果可以承受随机性能损失,那么对于较小的代码和更快的执行,可以省略该计算.
我的生成器,0x778B(adc),0x4A8B(eor)种子
根据我的测量结果,这是非常优质的种子之一.
为了找到具有良好相关性的种子,我建立了一个小程序,可以在某种程度上分析它们,就像Galois和我的一样.该程序精确定位了"高质量"的例子,然后我测试了其中几个并从中选择了一个.
一些结论:
伽罗瓦发电机似乎比我的更坚硬.在所有相关图上,可以观察到明确的几何图案(一些种子产生"棋盘"图案,这里未示出),即使它不是由线组成的.我的生成器也显示模式,但随着更多代,它们的定义变得越来越少.
Galois生成器的一部分结果包括高字节中的位似乎本质上是刚性的,我的生成器似乎没有这种属性.这是一个弱假设,但可能需要更多的研究(看看这对于Galois发电机是否总是如此,而不是我的其他位组合).
伽罗瓦发电机缺少零(最大周期为2 ^ 16-1).
截至目前,不可能为20位以上的发电机生成一组良好的种子.
后来我可能会更深入地寻求用Diehard测试发电机,但到目前为止,缺乏为它产生足够大种子的能力使得它变得不可能.