Here's my attempt at a random number generator optimized for 6502. An 8 bit random number is returned in A. It needs 7 bytes of RAM (preferably zero page), and has a period guaranteed to be at least 32 bits. It passes Dieharder and PractRand tests (up to at least 4GB of output).
I would imagine some starting seeds would go farther than others? What starting seed did you use to get the 4 GB output?
Is your algorithm based on math? What is the principle in this case? Or did you create randomly by trial and error?
A lot of trial and error, and then using the errors to refine my intuition. There's also some math involved, but I didn't realize that until it was already somewhat successful. Particularly, a chain of ADC instructions like this results in a maximum length permuted counter that will go through all possible states, but in a randomish order (provided that initial input is odd, and carry flag is cleared). The problem with just a simple chain of ADCs is that the lower order bits are quite regular, so I mixed in some EORs to try to break that pattern, and then used PractRand to see if it was successful.
The "magic" $45 constant input isn't very critical. Other odd values will work too.
Could you give us a vector test, the 50 first bytes with this seed ?
Arlet, i've not the same results with seed: .byte $00,$00,$00,$00,$00,$00,$00
How do you create the next byte? do you call the first line $100D for each new byte ?
Oops. I see that something went wrong in my test code. I used some C macros to emulate the ADC instruction, and didn't use enough parentheses.
Unfortunately, there's no easy way to fix the 6502 code to do the same.
Fortunately, even though my output was all wrong, the actual 6502 code was working fine for the intended purpose. I have fixed my emulation, and the random number output still passes PractRand (up to 16 GB right now, and still going).
Oops. I see that something went wrong in my test code. I used some C macros to emulate the ADC instruction, and didn't use enough parentheses.
Unfortunately, there's no easy way to fix the 6502 code to do the same.
Fortunately, even though my output was all wrong, the actual 6502 code was working fine for the intended purpose. I have fixed my emulation, and the random number output still passes PractRand (up to 16 GB right now, and still going).
#define ADD( a, b ) \
do { \
x = a + (b); \
a = x; \
} while (0)
#define ADC( a, b ) \
do { \
x = a + (b) + (x >> 8) % 2; \
a = x; \
} while (0)
Is it guarranteed that 'a' and 'b' are only 8 bits wide? You didn't include the definitions of s0..s6. The truncation is important though because if 'a' could store more than 8 bits, then a future add operation might pick up the extra bit and feed it into the carry calculation.
Is it guarranteed that 'a' and 'b' are only 8 bits wide? You didn't include the definitions of s0..s6. The truncation is important though because if 'a' could store more than 8 bits, then a future add operation might pick up the extra bit and feed it into the carry calculation.
Yes. All s0..s6 variables are declared as uint8_t type.
By the way, in case it wasn't clear, the code has been fixed. The problem was the missing parentheses around the 'b' in the macro. Everything works now, and the original 6502 code is still good.
Here's my attempt at a random number generator optimized for 6502. An 8 bit random number is returned in A. It needs 7 bytes of RAM (preferably zero page), and has a period guaranteed to be at least 32 bits. It passes Dieharder and PractRand tests (up to at least 4GB of output).
I find this quite intriguing! I ported it to BBC Basic so I could easily see how the state vector evolves (especially with numbers other than 0x45)
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.
