Page 4 of 17
Re: Random-number generation
Posted: Mon Mar 20, 2023 9:54 pm
by IamRob
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?
Re: Random-number generation
Posted: Mon Mar 20, 2023 11:55 pm
by Alex1
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 ?
seed: .byte $CA,$7E,$67,$9F,$BC,$DE,$DA
Re: Random-number generation
Posted: Tue Mar 21, 2023 5:46 am
by Arlet
I would imagine some starting seeds would go farther than others? What starting seed did you use to get the 4 GB output?
I used all zeroes for testing.
Re: Random-number generation
Posted: Tue Mar 21, 2023 5:49 am
by Arlet
With all zeroes, my output looks like this:
Code: Select all
00000000 00 8a a8 73 86 ae 5f e0 ac 63 5d 97 47 42 4a c5 |...s.._..c].GBJ.|
00000010 40 64 e5 05 19 68 42 f1 d6 44 88 47 12 b8 63 3c |@d...hB..D.G..c<|
00000020 72 84 75 ca 14 8f 28 9b 16 ef 62 b0 9a a6 74 64 |r.u...(...b...td|
00000030 84 3d 1a 30 03 e2 40 cd 49 3d 87 67 ec 86 ea 75 |.=.0..@.I=.g...u|
With $CA,$7E,$67,$9F,$BC,$DE,$DA as seed, I get:
Code: Select all
00000000 cf d7 0e 50 ff 8e 84 05 6d 34 4f d6 1d 9a 2c 29 |...P....m4O...,)|
00000010 19 ca 52 38 83 ca f6 ad 15 7a 36 e9 fb ea bf b6 |..R8.....z6.....|
00000020 9a 4e 13 63 f4 87 0e ee 40 74 0e 78 b4 e5 78 94 |.N.c....@t.x..x.|
00000030 93 25 8a be 89 56 19 09 b5 14 7b 5f 16 3f a6 2e |.%...V....{_.?..|
(Fixed)
Re: Random-number generation
Posted: Tue Mar 21, 2023 2:19 pm
by Alex1
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 ?
Here is my code first byte:
- Sélection_011.png (12.56 KiB) Viewed 3131 times
- Sélection_012.png (6 KiB) Viewed 3131 times
Second byte:
- Sélection_013.png (4.87 KiB) Viewed 3131 times
Re: Random-number generation
Posted: Tue Mar 21, 2023 3:29 pm
by Arlet
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).
Re: Random-number generation
Posted: Tue Mar 21, 2023 3:42 pm
by Alex1
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).
Can you paste your C code ?
Re: Random-number generation
Posted: Tue Mar 21, 2023 3:50 pm
by Arlet
Code: Select all
#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)
uint16_t x;
while( 1 )
{
ADD( s0, 0x45 );
ADC( s1, s0 );
ADC( s2, s1 );
ADC( s3, s2 );
ADC( s4, s3 ^ s6 );
ADC( s5, s4 );
ADC( s6, s5 );
putchar( s6 ^ s4 );
}
Re: Random-number generation
Posted: Tue Mar 21, 2023 3:52 pm
by Arlet
PractRand fails hard after 64 GB, but that's not really a huge surprise given that the guaranteed period is only 4GB. Good enough for 6502 work.
Code: Select all
rng=RNG_stdin, seed=unknown
length= 16 gigabytes (2^34 bytes), time= 255 seconds
no anomalies in 315 test result(s)
rng=RNG_stdin, seed=unknown
length= 32 gigabytes (2^35 bytes), time= 495 seconds
Test Name Raw Processed Evaluation
[Low1/8]Gap-16:B R= +5.9 p = 6.2e-5 mildly suspicious
...and 327 test result(s) without anomalies
rng=RNG_stdin, seed=unknown
length= 64 gigabytes (2^36 bytes), time= 982 seconds
Test Name Raw Processed Evaluation
BCFN(2+0,13-0,T) R= +92.2 p = 7.6e-49 FAIL !!!!
BCFN(2+1,13-0,T) R=+105.0 p = 1.0e-55 FAIL !!!!
BCFN(2+2,13-0,T) R= +97.2 p = 1.6e-51 FAIL !!!!
....(many more fails)...
Re: Random-number generation
Posted: Tue Mar 21, 2023 3:55 pm
by Arlet
By the way, I have fixed the test vectors above.
Re: Random-number generation
Posted: Tue Mar 21, 2023 4:23 pm
by gfoot
Code: Select all
#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.
Re: Random-number generation
Posted: Tue Mar 21, 2023 4:24 pm
by Arlet
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.
Re: Random-number generation
Posted: Tue Mar 21, 2023 4:39 pm
by BigEd
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)
Code: Select all
10 DIM seed 8: !seed=0: !(seed+4)=0
20 DIM c 99: P%=c
30 [ OPT 0
40 CLC
50 LDA #&45
60 ADC seed+0: STA seed+0
70 ADC seed+1: STA seed+1
80 ADC seed+2: STA seed+2
90 ADC seed+3: STA seed+3: EOR seed+6
100 ADC seed+4: STA seed+4
110 ADC seed+5: STA seed+5
120 ADC seed+6: STA seed+6: EOR seed+4
130 RTS
140 ]
150 FOR i=1 TO 20
160 A%=255 AND USRc
170 PRINT~A%,~!(seed+4),~!seed
180 NEXT
>
>RUN
0 454545 45454545
8A EEA964 5A14CF8A
A8 E0F248 DB39ECF
73 AFCEDC 7466B314
86 A2F324 E7730C59
AE 62BFCC 51DAA9E
5F C15E9E B0AB8DE3
E0 92D172 1261B628
AC DB4877 9785236D
63 C3E8A0 F25AD5B2
5D 27637A 1A27CCF7
97 7149E6 4B31093C
47 19A85E 6BB8A81
42 2A1068 130C50C6
4A F3C9B9 7B685C0B
C5 D9E61C 9014AC50
40 1B415B E6564195
64 FBE09F 58721BDA
E5 7B7F9E 5AD3B1F
5 C246C7 524C9F64
>
If we change 0x45 to 0x01 it's not too hard to follow the first round or two
Code: Select all
RUN
0 10101 1010101
2 70605 5040302
17 1A130D F0A0603
35 735946 23140A04
Re: Random-number generation
Posted: Tue Mar 21, 2023 5:04 pm
by Alex1
Here is the detailed code for educational purpose.
// ARLET RANDOM C CODE
#include <stdint.h>
#include <stdio.h>
void main()
{
// uint8_t seed[7]={0xca,0x7e,0x67,0x9f,0xbc,0xde,0xda}, rndbyte, carry;
uint8_t seed[7]={0,0,0,0,0,0,0}, rndbyte, carry;
unsigned long i,z;
z=0xffffffff;
for (i=0;i<20;i++)
{
carry=0;
rndbyte=0x45;
if ((rndbyte+seed[0])>255) {carry=1;} else {carry=0;}
rndbyte=(rndbyte+seed[0]);
seed[0]=rndbyte;
rndbyte=(rndbyte+carry);
if ((rndbyte+seed[1])>255) {carry=1;} else {carry=0;}
rndbyte=(rndbyte+seed[1]);
seed[1]=rndbyte;
rndbyte=(rndbyte+carry);
if ((rndbyte+seed[2])>255) {carry=1;} else {carry=0;}
rndbyte=(rndbyte+seed[2]);
seed[2]=rndbyte;
rndbyte=(rndbyte+carry);
if ((rndbyte+seed[3])>255) {carry=1;} else {carry=0;}
rndbyte=(rndbyte+seed[3]);
seed[3]=rndbyte;
rndbyte=(rndbyte^seed[6]);
rndbyte=(rndbyte+carry);
if ((rndbyte+seed[4])>255) {carry=1;} else {carry=0;}
rndbyte=(rndbyte+seed[4]);
seed[4]=rndbyte;
rndbyte=(rndbyte+carry);
if ((rndbyte+seed[5])>255) {carry=1;} else {carry=0;}
rndbyte=(rndbyte+seed[5]);
seed[5]=rndbyte;
rndbyte=(rndbyte+carry);
if ((rndbyte+seed[6])>255) {carry=1;} else {carry=0;}
rndbyte=(rndbyte+seed[6]);
seed[6]=rndbyte;
rndbyte=(rndbyte^seed[4]);
printf("%0.2X %0.2X %0.2X %0.2X %0.2X %0.2X %0.2X = %0.2X\n", seed[0], seed[1], seed[2], seed[3], seed[4], seed[5], seed[6], rndbyte);
// printf("%0.2X ",rndbyte);
}
}
- Sélection_014.png (13.52 KiB) Viewed 3114 times
Re: Random-number generation
Posted: Tue Mar 21, 2023 5:10 pm
by Arlet
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.