Random-number generation

[Alex1]

Arlet wrote:

Quote:

so I could easily see how the state vector evolves (especially with numbers other than 0x45)

If you have a real random source, you could remove the LDA #$45 line, and just call the subroutine with a value in A. Even if it's a mediocre source of randomness, once it makes its way through the state machine, it will be pretty good. Just make sure you get a regular supply of odd numbers in there, or set bit 0 yourself.

It's an interesting algorithm, I've never seen it in the books and it passes all the statistical tests. How did you come up with this idea?

[Arlet]

Quote:

How did you come up with this idea?

Basically by looking at the 6502 instruction set, and looking for anything that could be helpful. The ADC instruction jumps out as the most useful one. If you add a number to itself, you have a rotate left, which means that you can build a LFSR with it. Internally, it's made from full adders, which have XOR, AND, OR as building blocks, so it's quite a mixed bag. I started building a chain of ADCs and noticed some interesting results, but not quite good enough by itself. Then I started looking at ways to mix things up a bit, so went back to the instruction set, and picked EOR as a companion. I also tried the rotate and shift instructions, but they all mess up the carry flag.

With PractRand, it's easy to test a few ideas. If they suck, then it only takes 5 seconds before it tells you. I started with the basic ADC chain, and then inserted a few EORs here and there.

[Alex1]

Arlet, what command line do you use with PractRand to test your PRNG ?

[Arlet]

my_test | RNG_test stdin

[Alex1]

Arlet wrote:

my_test | RNG_test stdin

is it the same as my_test | RNG_test stdin8 ?

[Arlet]

I think stdin8 is more optimized for finding faults in 8 bit wide inputs, so that's probably better.

[Alex1]

Arlet wrote:

Quote:

How did you come up with this idea?

Basically by looking at the 6502 instruction set, and looking for anything that could be helpful. The ADC instruction jumps out as the most useful one. If you add a number to itself, you have a rotate left, which means that you can build a LFSR with it. Internally, it's made from full adders, which have XOR, AND, OR as building blocks, so it's quite a mixed bag. I started building a chain of ADCs and noticed some interesting results, but not quite good enough by itself. Then I started looking at ways to mix things up a bit, so went back to the instruction set, and picked EOR as a companion. I also tried the rotate and shift instructions, but they all mess up the carry flag.

With PractRand, it's easy to test a few ideas. If they suck, then it only takes 5 seconds before it tells you. I started with the basic ADC chain, and then inserted a few EORs here and there.

The problem is that since it is not based on sound mathematics, we do not know if there are loops for some seeds or not. It would be necessary to test all the seeds of 1 to $FFFFFF and check if for each seed we obtain 2^32 bytes without loop. So you should run rng_test for each 2^32 seed.

[Arlet]

Alex1 wrote:

The problem is that since it is not based on sound mathematics, we do not know if there are loops for some seeds or not. It would be necessary to test all the seeds of 1 to $FFFFFF and check if for each seed we obtain 2^32 bytes without loop. So you should run rng_test for each 2^32 seed.

Not quite. You can prove that the ADC chain goes through all possible states before repeating. That is this part, which has 32 bits.

Code: Select all

        ADD( s0, 0x45 );
        ADC( s1, s0 );
        ADC( s2, s1 );
        ADC( s3, s2 );

This property breaks with the next line, because it has a feedback from s6, resulting in chaotic behavior and shorter loops.

Code: Select all

ADC( s4, s3 ^ s6 );

Whatever happens in s4, s5, s6 is random, but s0-s3 are counting systematically. You can see this by skipping ahead 256 steps, and notice that every time s1 is incremented by same amount. This can be explained mathematically. Starting with s0=0, after 256 steps, the variable 's0' will be back at 0, having gone through every other number exactly once. That means that a value of 0+1+2+...+255 has been added to s1, which is equal to 255*256/2 = 32640 is equal to 128 modulo 256. So, without any carries, when s0 loops around, s1 will be 0x80 higher. Now, adding the carries, when you add 256 times 0x45, you will overflow exactly 0x45 times, producing 0x45 carries to s1. So, including the carries, s1 will be 0xc5 (mod 256) higher, and because that's an odd number, you need to repeat that 256 times before s1 is back at 0.

The same argument goes for s1->s2 and s2->s3.

[gfoot]

That's neat - you're proving first that the cycle length must be a multiple of 256 (so that s0 returns to zero), then that it must be a further multiple of 256 more (so that s1 returns to zero at the same time as s0), then x256 more so that s2 returns to zero at the same time, and finally another x256 so that s3 also returns to zero at this time. So the period is maximised and hence there are no short loops for these four bytes, every state is part of the same cycle, and the only thing you relied on was that the amount added to s0 each time was odd.

It's still not clear to me that we can guarantee that the rest of the longer chain of adds with feedback doesn't ever reduce this period at the output end, but I'm no expert on this!

[Arlet]

Quote:

It's still not clear to me that we can guarantee that the rest of the longer chain of adds with feedback doesn't ever reduce this period

During the 2^32 cycles where s0-s3 are guaranteed to get different values, s4-s6 will bounce along, and never get stuck in short loops, because it is constantly fed from the s0-s3 states that are producing 4GB of unique patterns.

Worst case is when you stop after 2^32 rounds, and then s4-s6 happen to have the same values as in the beginning, which makes 4GB the shortest possible period.

[Arlet]

Here's a version that only requires 6 bytes of RAM, and 1 less instruction. Also, just for fun, only uses ADC. Passes PractRand <= 4GB then fails hard.

Code: Select all

CLC
LDA #&45
ADC seed+0
STA seed+0
ADC seed+1
STA seed+1
ADC seed+2
STA seed+2
ADC seed+3
STA seed+3
ADC seed+4
ADC seed+5
STA seed+4
ADC seed+5
STA seed+5
ADC seed+4
ADC seed+2
RTS

Working Owlet BBC code

[BigEd]

Quick thought: if you take only the MSBits, or conversely only the LSBits, are they also adequately random as a bitstream?

[Arlet]

PractRand does extensive testing for isolated lower bits, so I would think so. It doesn't test the MSBits separately, I think, but I would expect those to be better quality.

For instance, this is a typical failure output message:

Code: Select all

[Low1/8]BCFN(2+6,13-0,T)          R= +30.4  p =  9.1e-16    FAIL           

The "Low1/8" part means that for each byte, the least significant bit was isolated, and all those single bits were then fed into the "BCFN" test.

[Arlet]

Got rid of one more instruction. First couple of output bytes don't look so good with all-zero seed value, but it still (barely) passes PractRand to 4GB. I don't think any more cycles can be removed unless you don't mind a somewhat lower quality (which could be fine for a lot of purposes).

Code: Select all

CLC
LDA #&45
ADC seed+0
STA seed+0
ADC seed+1
STA seed+1
ADC seed+2
STA seed+2
ADC seed+3
STA seed+3
EOR seed+4
ADC seed+5
STA seed+4
ADC seed+5
EOR seed+2
STA seed+5
RTS

BBC code

[Alex1]

I feel like there's a bug somewhere. I used my code in C (which is a literal translation of your 6502 code to C) and your code in C. I have the same output on both sides up to byte 326 and then it's different. My byte 326 is at $46 and yours is at $45. Do you know what could be the problem?

My C code :

Your C code:

And with your C code i've loops :

Quote:

Found '008AA873' at index 0 !
Found '008AA873' at index 11EC9D07 !
Found '008AA873' at index 36982356 !
Found '008AA873' at index B20751BF !

But not with my C code.