这是旧的观念，但是从那以后我不能让周围发现了一些解决它提出的问题相当好办法。所以，我发明（见下文）非常紧凑，而且在我看来，合理地进行PRNG，但我不能找出算法在大位深度打造适合的种子值吧。我目前的解决方案是简单地暴力破解，它的运行时间为O（n ^ 3）。

An old idea, but ever since then I couldn't get around finding some reasonably good way to solve the problem it raised. So I "invented" (see below) a very compact, and in my opinion, reasonably well performing PRNG, but I can't get to figure out algorithms to build suitable seed values for it at large bit depths. My current solution is simply brute-forcing, it's running time is O(n^3).

发电机

我的想法来自异或水龙头（基本上的LFSR ）用于声音产生一些旧的8位机。我拨弄着XOR作为一个C64基地，试图拼凑运codeS，和经验丰富的结果。最后的工作液是这样的：

My idea came from XOR taps (essentially LFSRs) some old 8bit machines used for sound generation. I fiddled with XOR as a base on a C64, tried to put together opcodes, and experienced with the result. The final working solution looked like this:

asl
adc #num1
eor #num2

这是5个字节的6502.有了一个很好的选择NUM1与NUM2，在累加器它遍历所有的256个值在一个看似随机的顺序，也就是说，它看起来使用时填充屏幕相当随机的（我写的有点256B演示回来然后在此）。有40个适合NUM1和放大器; NUM2对这个，让所有正派寻找序列。

This is 5 bytes on the 6502. With a well chosen num1 and num2, in the accumulator it iterates over all 256 values in a seemingly random order, that is, it looks reasonably random when used to fill the screen (I wrote a little 256b demo back then on this). There are 40 suitable num1 & num2 pairs for this, all giving decent looking sequences.

这个概念可以很好地概括，如果pssed纯C EX $ P $，它可能看起来像这样（位是位深度的顺序）：

The concept can be well generalized, if expressed in pure C, it may look like this (BITS being the bit depth of the sequence):

r = (((r >> (BITS-1)) & 1U) + (r << 1) + num1) ^ num2;
r = r & ((1U<<BITS)-1U);

此C code是长，因为它是广义，并且即使一个将使用无符号整数的全部深度，C就没有必要的进位逻辑移位的高比特传送到附加操作。

This C code is longer since it is generalized, and even if one would use the full depth of an unsigned integer, C wouldn't have the necessary carry logic to transfer the high bit of the shift to the add operation.

对于一些性能分析和比较，请参见下面的问题（S）之后。

For some performance analysis and comparisons, see below, after the question(s).

的问题/问题（S）

的核心问题与发电机是找到合适的NUM1和NUM2这将使它迭代给定比特深度的整个可能序列。在本节结束时，我附上我的code这只是蛮力迫使它。它会在合理的时间内完成多达12位，你可能会等待所有16位（也有对于5736可能配对的方式，用一个通宵的全搜索前一段时间收购），你可能会得到一些20位如果你有耐心。但为O（n ^ 3），真是讨厌...

The core problem with the generator is finding suitable num1 and num2 which would make it iterate over the whole possible sequence of a given bit depth. At the end of this section I attach my code which just brute-forces it. It will finish in reasonable time for up to 12 bits, you may wait for all 16 bits (there are 5736 possible pairs for that by the way, acquired with an overnight full search a while ago), and you may get a few 20 bits if you are patient. But O(n^3) is really nasty...

（谁将拿到找到的第一个完整的32位序列？）

(Who will get to find the first full 32bit sequence?)

其他有意思的问题而出现：

Other interesting questions which arise:

对于这两种NUM1与NUM2只有奇数值能够生产全序列。为什么？这可能不是硬（简单的逻辑，我猜的），但我从来没有合理的证明了这一点。

For both num1 and num2 only odd values are able to produce full sequences. Why? This may not be hard (simple logic, I guess), but I never reasonably proved it.

有沿NUM1镜像属性（外接值），即，如果A与给定的​​'B'NUM2给出了一个完整的序列，则2补'一'（在给定的位深度）与同NUM2也是全序列。我只发现这确实发生了所有我计算的全代。

There is a mirroring property along num1 (the add value), that is, if 'a' with a given 'b' num2 gives a full sequence, then the 2 complement of 'a' (in the given bit depth) with the same num2 is also a full sequence. I only observed this happening reliably with all the full generations I calculated.

第三个有趣的特性是，所有的NUM1和放大器; NUM2对所得的序列似乎以形成适当的圆，也就是至少是数字零似乎总是一个圆的一部分。如果没有这个属性我的蛮力搜索会死在一个无限循环。

A third interesting property is that for all the num1 & num2 pairs the resulting sequences seem to form proper circles, that is, at least the number zero seems to be always part of a circle. Without this property my brute force search would die in an infinite loop.

奖励：是这样的PRNG之前已经知道的？ （我只是重新发明了它）？

Bonus: Was this PRNG already known before? (and I just re-invented it)?

这里是蛮力搜索的code（C）：

And here is the brute force search's code (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;
}

这，来显示它正在工作，每次迭代将输出后，发现对，如果它的序列长度等于或大于previous。修改位常数其他深度序列。

This, to show it is working, after each iteration will output the pair found if it's sequence length is equal or longer than the previous. Modify the BITS constant for sequences of other depths.

种子狩猎

我没有与种子一些图表。这是一个良好的形象，显示所有的9位序列长度：

I did some graphing relating to the seeds. Here is a nice image showing all the 9bit sequence lengths:

白色的小点是全长序列，X轴是NUM1（添加），Y轴是NUM2（XOR），亮的点，时间越长的序列。其他位深度看在模式非常相似：他们似乎都被分解为16个重大瓷砖有两种模式的重复和镜像。的瓦片的相似性是不完整的，例如高于从向上左上角到右下角的对角线是清晰可见的，而它的相对不存在，但对于全长序列这个属性似乎是可靠的。

The white dots are the full length sequences, X axis is for num1 (add), Y axis is for num2 (xor), the brighter the dot, the longer the sequence. Other bit depth look very similar in pattern: they all seem to be broken up to sixteen major tiles with two patterns repeating with mirroring. The similarity of the tiles is not complete, for example above a diagonal from the up-left corner to the bottom-right is clearly visible while it's opposite is absent, but for the full-length sequences this property seems to be reliable.

就凭这有可能减少工作不是由previous假设甚至更多，但仍然为O（n ^ 3）...

Relying on this it is possible to reduce the work even more than by the previous assumptions, but that's still O(n^3)...

性能分析

由于电流可能要产生的最长的序列是24位：我的电脑上它需要在约5小时至暴力破解全24位序列为此。这还只是马马虎虎真正的PRNG的测试，如死硬，所以到现在为止我比较过去了一个自己的方法。

As of current the longest sequences possible to be generated are 24bits: on my computer it takes at about 5 hours to brute-force a full 24bit sequence for this. This is still just so-so for real PRNG tests such as Diehard, so as of now I rather gone by an own approach.

首先，它重要的是要了解发电机的作用。这绝不会是一个很好的发电机为它的简单，它的目标是相当产生像样的数字速度极快。在这个地区不需要乘法/除法运算，一个伽罗瓦线性反馈移位寄存器可以产生类似的性能。所以，我的发电机是它是否能够超越这个有什么用处。

First it's important to understand the role of the generator. This by no means would be a very good generator for it's simplicity, it's goal is rather to produce decent numbers blazing fast. On this region not needing multiply / divide operations, a Galois LFSR can produce similar performance. So my generator is of any use if it is capable to outperform this one.

我进行的测试都是16bit的发电机。我选择了这个深度，因为它提供了一个有用的序列长度，同时该数字可能仍然在2 8位部分被分解使得能够present各种比特精确图形视觉分析

The test I performed were all of 16bit generators. I chose this depth since it gives an useful sequence length while the numbers may still be broken up in two 8bit parts making it possible to present various bit-exact graphs for visual analysis.

测试的核心所寻找的沿previous相关和当前生成的数字。为此，我使用X：Y地块，其中previous代是Y，目前在X，既打破低/高部件如上面提到的两个图形。我创建能够绘制这些台阶实时所以也使人们有可能大致检查数字是如何相互跟随，图表如何填补方案。这里显然只有最终结果作为发电机运行通过其全部2 ^ 16或2 ^ 16-1（伽罗瓦）循环

The core of the tests were looking for correlations along previous and currently generated numbers. For this I used X:Y plots where the previous generation was the Y, the current the X, both broken up to low / high parts as above mentioned for two graphs. I created a program capable of plotting these stepped in real time so to also make it possible to roughly examine how the numbers follow each other, how the graphs fill up. Here obviously only the end results are shown as the generators ran through their full 2^16 or 2^16-1 (Galois) cycle.

字段的解释是：

该图像由8X2 256x256的图，使得总的图像尺寸2048x512（检查他们在原来的大小）。

The images consist 8x2 256x256 graphs making the total image size 2048x512 (check them at original size).

左上图只是证实，确实是一个完整的序列，绘制，它只是一个 X = R％256; Y = R / 256; 剧情

The top left graph just confirms that indeed a full sequence was plotted, it is simply an X = r % 256; Y = r / 256; plot.

左下图显示每第二数目仅绘制方式相同的顶部，只是在确认号码发生相当随机

The bottom left graph shows every second number only plotted the same way as the top, just confirming that the numbers occur reasonably randomly.

从第二张图的上面一排是高字节的相关性图表。第一他们使用了previous代，下跳过一个号码（因此采用第二previous代），等等，直到第七previous代

From the second graph the top row are the high byte correlation graphs. The first of them uses the previous generation, the next skips one number (so uses 2nd previous generation), and so on until the 7th previous generation.

从第二底行是低字节相关图表，组织为上述相同的方式

From the second the bottom row are the low byte correlation graphs, organized the same way as above.

伽罗瓦发生器，0xB400抽头设置的

这是在维基百科伽罗瓦例如发现发电机。它的性能是不是最差的，但它仍然是绝对算不上好。

This is the generator found in the Wikipedia Galois example. It's performance is not the worst, but it is still definitely not really good.

伽罗瓦发生器，0xA55A抽头设置的

一个体面的伽罗瓦种子我发现。需要注意的是16位数字的低位部分似乎是很多比上面的好，但我找不到任何伽罗瓦的种子，这将模糊化了的高字节。

One of the decent Galois "seeds" I found. Note that the low part of the 16bit numbers seem to be a lot better than the above, however I couldn't find any Galois "seed" which would fuzz up the high byte.

我的发电机，0x7F25（ADC），0x00DB（EOR）的种子的

这是我最大的发电机，其中EOR值的高字节为零。自那时以来，这个计算可以省略小code和更快的执行，如果随机性性能的损失是可以承受的极限高字节是8位机是有用的。

This is the best of my generators where the high byte of the EOR value is zero. Limiting the high byte is useful on 8bit machines since then this calculation can be omitted for smaller code and faster execution if the loss of randomness performance is affordable.

我的发电机，0x778B（ADC），0x4A8B（EOR）的种子的

这是很好的优质种子通过我的测量之一。

This is one of the very good quality seeds by my measurements.

要找到种子具有良好的相关性，我建立了一个小程序，它会分析它们在一定程度上，以同样的方式进行伽罗瓦和矿山。 好品质的例子是由该程序明确指出，然后我测试了其中几个，选择了一个不同于

To find seeds with good correlation, I built a small program which would analyse them to some degree, the same way for Galois and mine. The "good quality" examples were pinpointed by that program, and then I tested several of them and selected one from those.

一些结论：

伽罗瓦发生器似乎比我更坚硬。在所有的相关的图表确定的几何图案是可观察到的（一些种子生产的棋盘图案，此处未显示），即使它不是由行。我的发电机也显示模式，但更多的后代，他们越来越少定义。

The Galois generator seems to be more rigid than mine. On all the correlation graphs definite geometrical patterns are observable (some seeds produce "checkerboard" patterns, not shown here) even if it is not composed of lines. My generator also shows patterns, but with more generations they grow less defined.

的伽罗瓦产生的结果的一部分，其中包括在高字节中的位似乎是天生的刚性哪个属性似乎是从我的发电机缺席。这是一个弱假设，但可能需要一些更多的研究（看看这永远是那么的伽罗瓦发电机，而不是与我在其他位组合）。

A portion of the Galois generator's result which include the bits in the high byte seems to be inherently rigid which property seems to be absent from my generator. This is a weak assumption yet probably needing some more research (to see if this is always so with the Galois generator and not with mine on other bit combinations).

伽罗瓦生成缺少零（最长时长为2 ^ 16-1）。

The Galois generator lacks zero (maximal period being 2^16-1).

截至目前，这是不可能生成一组种子为我的生成超过20位。

As of now it is impossible to generate a good set of seeds for my generator above 20 bits.

后来我可能在这个问题上得到更深层次的寻求测试与死硬的发电机，但截至目前缺乏产生足够大的种子，它使不可能的能力。

Later I might get in this subject deeper seeking to test the generator with Diehard, but as of now the lack of the ability of generating large enough seeds for it makes it impossible.

推荐答案

这是某种形式的非线性移位反馈寄存器。我不知道它已被用作例如，但它类似于线性反馈移位寄存器几分。阅读这篇维基百科页面作一介绍LSFRs。它们经常用于在伪随机数产生

This is some form of a non-linear shift feedback register. I don't know if it has been used as such, but it resembles linear shift feedback registers somewhat. Read this Wikipedia page as an introduction to LSFRs. They are used frequently in pseudo random number generation.

然而，你的伪随机数发生器是在固有地坏有一个previously生成的号码的最高阶位和产生下一个数的最低位之间的线性相关。你却将最高位B发出，然后新的电话号码的最低位将是XOR或B，加常数NUM1和异或不变NUM2的最低位的最低位，因为二进制加法相当于独家或在最低位。最有可能的PRNG有其他类似的缺陷。创造良好的PRNG是很难的。

However, your pseudo random number generator is inherently bad in that there is a linear correlation between the highest order bit of a previously generated number and the lowest order bit of a number generated next. You shift the highest bit B out, and then the lowest order bit of the new number will be the XOR or B, the lowest order bit of the additive constant num1 and the lowest order bit of the XORed constant num2, because binary addition is equivalent to exclusive or at the lowest order bit. Most likely your PRNG has other similar deficiencies. Creating good PRNGs is hard.

不过，我必须承认，C64 code是令人愉快紧凑！

However, I must admit that the C64 code is pleasingly compact!