Finding seeds for a 5 byte PRNG

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).

The generator

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

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.

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);

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.

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

The problem / question(s)

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...

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

Other interesting questions which arise:

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.

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.

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.

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

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): %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;
}

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.

Seed hunting

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

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.

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

Performance analysis

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.

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.

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.

The explanation of the fields:

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

The top left graph just confirms that indeed a full sequence was plotted, it is simply an X = r % 256; Y = r / 256; 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.

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.

Galois generator, 0xB400 tap set

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.

Galois generator, 0xA55A tap set

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.

My generator, 0x7F25 (adc), 0x00DB (eor) seed

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.

My generator, 0x778B (adc), 0x4A8B (eor) seed

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.

Some conclusions:

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).

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

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.

---

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.

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.

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

链接地址: http://www.djcxy.com/p/37270.html

上一篇: 理解这个16

下一篇: 寻找5字节PRNG的种子