6502.org • View topic - Random-number generation

View unanswered posts | View active topics

Board index » 6502.org Users Forum » Programming

All times are UTC

Random-number generation

Page 12 of 17

[ 245 posts ]

Go to page Previous 1 ... 9, 10, 11, 12, 13, 14, 15 ... 17 Next

Previous topic | Next topic

Author

Message

dmsc

Post subject: Re: Random-number generation

Posted: Tue Apr 18, 2023 11:04 pm

Joined: Mon Sep 17, 2018 2:39 am
Posts: 138

Hi!

BigEd wrote:

I was thinking specifically that with only 4 bytes of state, you can at best get a permutation of 2^32 outputs. You can't get the same 32 bit output twice. So I'd expect such a setup to fail these statistical tests in a much bigger way than a 5 byte setup.

The trick is that you don´t output the full 32 bits of "mangled state", you only output 8 bits each time. This means that you don´t see the permutation, and with a proper mixing of all the state bits you can easily pass statistical tests up to 2^32/4 = 2^30 samples. And IMHO, 2^30 outputs is big enough for any 6502 use - think that with 200 cycles between RNG calls, and a 12MHz CPU clock, you would need five hours to start to notice something bad.

For comparison, the RNG in the Atari 8-bit BASIC uses a 17-bit hardware LFSR running at the CPU frequency, and "hopes" that reads of the hw register are not correlated enough, but in reality the quality of the generated numbers is very bad.

Have Fun!

Top

Arlet

Post subject: Re: Random-number generation

Posted: Wed Apr 19, 2023 3:41 am

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands

Here's one that's even smaller than the 'minimal-6502.asm', with slightly less performance, but 4 cycles saved. It uses 4 bytes for guaranteed 4GB period, plus 1 extra state byte to improve randomness.

Code:

CLC 
LDA #$41
ADC state+0 ; iterate state
STA state+0 ;
ADC state+1 ;
STA state+1 ;
ADC state+2 ;
STA state+2 ;
ADC state+3 ;
STA state+3 ; end of iterator
ADC state+4 ; output function with feedback
ASL 
ADC state+3
STA state+4
EOR state+2
RTS 

I made a few attempts at reducing the code even more, but they all made things dramatically worse.
Owlet code

Last edited by Arlet on Wed Apr 19, 2023 6:13 am, edited 2 times in total.

Top

dmsc

Post subject: Re: Random-number generation

Posted: Wed Apr 19, 2023 5:00 am

Joined: Mon Sep 17, 2018 2:39 am
Posts: 138

Hi!

Arlet wrote:

Code:

CLC 
LDA #$45
ADC state+0 ; iterate state
STA state+0 ;
ADC state+1 ;
STA state+1 ;
ADC state+2 ;
STA state+2 ;
ADC state+3 ;
STA state+3 ; end of iterator
ADC state+4 ; output function with feedback
ASL 
ADC state+3
STA state+4
EOR state+2
RTS 

Very good!

Passes PractRand up to 2^29, IMHO, very good performance for such a tiny code:

Code:

$ minisim arlet8-minimal.65 | ./conv8 | ../../pr-095/RNG_test stdin8 -te 1 -tlmin 10 -tlmax 50 -tlmaxonly -multithreaded
RNG_test using PractRand version 0.95
RNG = RNG_stdin8, seed = unknown
test set = expanded, folding = standard (8 bit)

rng=RNG_stdin8, seed=unknown
length= 1 kilobyte (2^10 bytes), time= 0.1 seconds
  no anomalies in 16 test result(s)

rng=RNG_stdin8, seed=unknown
length= 2 kilobytes (2^11 bytes), time= 0.3 seconds
  no anomalies in 30 test result(s)

.... snip ....

rng=RNG_stdin8, seed=unknown
length= 512 megabytes (2^29 bytes), time= 203 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low1/8]FPF-14+6/16:all           R=  +6.1  p =  3.5e-5   unusual          
  [Low1/8]Gap-16:A                  R=  +5.9  p =  1.7e-4   unusual          
  ...and 313 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 381 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low1/8]FPF-14+6/64:(0,14-0)      R=  +8.4  p =  2.4e-7   mildly suspicious
  [Low1/8]FPF-14+6/64:all           R= +10.5  p =  2.2e-9    VERY SUSPICIOUS 
  [Low1/8]FPF-14+6/32:(0,14-0)      R=  +9.0  p =  5.8e-8   suspicious       
  [Low1/8]FPF-14+6/32:all           R=  +9.4  p =  2.5e-8   very suspicious  
  [Low1/8]FPF-14+6/16:(0,14-0)      R=  +6.8  p =  6.0e-6   unusual          
  [Low1/8]FPF-14+6/16:all           R=  +8.7  p =  1.1e-7   very suspicious  
  [Low1/8]Gap-16:A                  R= +11.9  p =  1.2e-9    VERY SUSPICIOUS 
  ...and 328 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 774 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low1/8]FPF-14+6/64:(0,14-0)      R= +12.6  p =  3.0e-11   VERY SUSPICIOUS 
  [Low1/8]FPF-14+6/64:(1,14-0)      R= +11.7  p =  1.9e-10  very suspicious  
  [Low1/8]FPF-14+6/64:all           R= +17.8  p =  3.6e-16    FAIL !         
  [Low1/8]FPF-14+6/32:(0,14-0)      R= +13.6  p =  3.7e-12   VERY SUSPICIOUS 
  [Low1/8]FPF-14+6/32:(1,14-0)      R=  +9.4  p =  2.7e-8   suspicious       
  [Low1/8]FPF-14+6/32:all           R= +17.4  p =  8.7e-16    FAIL !         
  [Low1/8]FPF-14+6/16:(0,14-0)      R= +10.3  p =  4.0e-9   very suspicious  
  [Low1/8]FPF-14+6/16:(1,14-0)      R=  +7.0  p =  4.4e-6   unusual          
  [Low1/8]FPF-14+6/16:(2,14-0)      R=  +8.3  p =  2.5e-7   mildly suspicious
  [Low1/8]FPF-14+6/16:all           R= +16.1  p =  1.4e-14    FAIL           
  [Low1/8]FPF-14+6/4:(0,14-0)       R=  +7.0  p =  4.2e-6   unusual          
  [Low1/8]FPF-14+6/4:all            R= +11.5  p =  2.6e-10   VERY SUSPICIOUS 
  [Low1/8]Gap-16:A                  R= +22.7  p =  8.7e-18    FAIL !         
  [Low1/8]Gap-16:B                  R= +11.6  p =  1.7e-9    VERY SUSPICIOUS 
  ...and 341 test result(s) without anomalies

Have Fun!

Top

Arlet

Post subject: Re: Random-number generation

Posted: Wed Apr 19, 2023 5:02 am

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands

I just edited the code a little bit. The constant has been changed from $45 to $41, and that seems to work a bit better.

Top

Arlet

Post subject: Re: Random-number generation

Posted: Wed Apr 19, 2023 6:17 am

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands

dmsc wrote:

Previously I tested Bob Jenkins 8-bit Small Fast PRNG, but it translates to bigger 6502 code and only passes PractRand 0.94, not 0.95, as it fails the new "mod3n(0):(0,9-6)" test at 2^18 bytes.

Is that the jsf8 code below ? This code uses a different strategy. It's not an iterator+output function, but a chaotic feedback function, which suffers from the problem that some bad seeds can cause short periods. They work around that problem by the "raninit" function that forces a restriction on possible seed values, so that they guarantee a long (but less than 4GB) period. The advantage of this method is that you have the potential for better randomness in fewer operations. However, the rot8() is not well suited to 6502, so the translation to 6502 assembly adds a bunch of cycles again.

It would be interesting to explore the concept, but starting from scratch with 6502 targeted operations. Edit: I tried a few things, but not much hope. The nice thing about the ADC/STA sequence is that the accumulator is already loaded with the value that will be used to modify the next state byte. If you try to do something like the code below, you're going to need some LDAs, which seem like a waste of time, because they are only moving data around, not actually changing it. Maybe there is a solution, but at best I would expect a tiny improvement in cycles, at the bigger cost of not being able to use any random seed

Code:

typedef uint8_t u1;
typedef struct ranctx { u1 a; u1 b; u1 c; u1 d; } ranctx;

#define rot8(x,k) (((x)<<(k))|((x)>>(8-(k))))
u1 ranval( ranctx *x ) {
    u1 e = x->a - rot8(x->b, 1);
    x->a = x->b ^ rot8(x->c, 4);
    x->b = x->c + x->d;
    x->c = x->d + e;
    x->d = e + x->a;
    return x->d;

void raninit( ranctx *x, u1 seed ) {
    x->a = 0xed, x->b = x->c = x->d = seed;
    for (u1 i=0; i<20; ++i) {
        (void)ranval(x);
    }
}

Top

Alex1

Post subject: Re: Random-number generation

Posted: Wed Apr 19, 2023 4:39 pm

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80

dmsc wrote:

Hi!
It is a "command line" Atari 8-bit simulator: https://github.com/dmsc/mini65-sim
Have Fun!

When i try to compile arlet-medium.asm with ca65 i've some erros like "Segment `STARTUP' does not exist"

Which command line do you use to compile arlet-medium.asm and did you add some code in the arlet-medium.asm ?

Top

dmsc

Post subject: Re: Random-number generation

Posted: Wed Apr 19, 2023 8:40 pm

Joined: Mon Sep 17, 2018 2:39 am
Posts: 138

Hi!

Alex1 wrote:

dmsc wrote:

Hi!
It is a "command line" Atari 8-bit simulator: https://github.com/dmsc/mini65-sim
Have Fun!

Code:

cl65 -tatari -Catari-asm.cfg arlet-medium.asm

This will produce an Atari 8-bit executable that the simulator can run.

Have Fun!

Top

Alex1

Post subject: Re: Random-number generation

Posted: Wed Apr 19, 2023 10:29 pm

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80

Thanks.

Last edited by Alex1 on Thu Apr 20, 2023 11:52 pm, edited 1 time in total.

Top

dmsc

Post subject: Re: Random-number generation

Posted: Wed Apr 19, 2023 10:46 pm

Joined: Mon Sep 17, 2018 2:39 am
Posts: 138

Hi!

Alex1 wrote:

dmsc wrote:

Hi!

Code:

cl65 -tatari -Catari-asm.cfg arlet-medium.asm

This will produce an Atari 8-bit executable that the simulator can run.

Thanks you for your answer but it doesn't work.

Inside arlet-medium.asm

Code:

prng:
    CLC
    LDA #$45
    ADC state+0
    STA state+0
    ADC state+1
    STA state+1
    ADC state+2
    STA state+2
    ADC state+3
    STA state+3
    ADC state+4
    STA state+4
    LDA state+5
    EOR state+7
    ADC state+4
    STA state+5
    ADC state+6
    STA state+6
    LDA state+7
    ASL
    ADC state+6
    STA state+7
    EOR state+2
    RTS
state:  .res    8

Code:

cl65 -tatari -catari-asm.cfg arlet-medium.asm

It produce only arlet-medium.o which is an object file, not an executable file.

Code:

./atarisim arlet-medium.o
./atarisim: error reading binary file.

You are using a lowercase "-c", that means "compile but don't link", the correct incantation is "-Catari-asm.cfg", with a uppercase "C", that means "use this configuration file".

Have Fun!

Top

Alex1

Post subject: Re: Random-number generation

Posted: Thu Apr 20, 2023 12:36 am

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80

@dmsc thanks for your answer.
BTW do you have a link for your conv8 converter ?

Top

Arlet

Post subject: Re: Random-number generation

Posted: Thu Apr 20, 2023 6:52 pm

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands

Instead of printing the output in hex and then piping through conv8, isn't it easier/faster just to putc the 8 bit binary ?

Top

Alex1

Post subject: Re: Random-number generation

Posted: Thu Apr 20, 2023 7:36 pm

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80

Arlet wrote:

Instead of printing the output in hex and then piping through conv8, isn't it easier/faster just to putc the 8 bit binary ?

Not on Atari : 0x9B from .asm is converted to 0x0D by Atari ROM on the pipe and 0x12 from .asm is converted to 0x2D on the pipe too. And then rng_test failed.
Same type of problem as on windows with 0x0D 0x0A but only 0x0A on linux.

Last edited by Alex1 on Thu Apr 20, 2023 8:05 pm, edited 1 time in total.

Top

Alex1

Post subject: Re: Random-number generation

Posted: Thu Apr 20, 2023 7:57 pm

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80

i found a solution, i modify this in the .asm code, no carriage return (to gain speed with one less character) :

Code:

  ; Generate and print numbers
loop:
        jsr     rand
        jsr     print_hex_byte
----> ; lda     #$9B
----> ; jsr     putc

        inc     cnt
        bne     loop
        inc     cnt+1
        bne     loop
        inc     cnt+2
        bne     loop
        inc     cnt+3
        bne     loop
        inc     cnt+4
        bne     loop
        inc     cnt+5
        bne     loop
        rts

and use xxd :

Code:

./atarisim arlet-medium.65 | xxd -r -p | rng_test stdin8 -te 1 -tlmin 10 -tlmax 50 -tlmaxonly -multithreaded

Seems to work. Do you confirm dmsc ?

Top

dmsc

Post subject: Re: Random-number generation

Posted: Thu Apr 20, 2023 8:31 pm

Joined: Mon Sep 17, 2018 2:39 am
Posts: 138

Hi!

Alex1 wrote:

i found a solution, i modify this in the .asm code, no carriage return (to gain speed with one less character) :

Code:

  ; Generate and print numbers
loop:
        jsr     rand
        jsr     print_hex_byte
----> ; lda     #$9B
----> ; jsr     putc

        inc     cnt
        bne     loop
        inc     cnt+1
        bne     loop
        inc     cnt+2
        bne     loop
        inc     cnt+3
        bne     loop
        inc     cnt+4
        bne     loop
        inc     cnt+5
        bne     loop
        rts

and use xxd :

Code:

./atarisim arlet-medium.65 | xxd -r -p | rng_test stdin8 -te 1 -tlmin 10 -tlmax 50 -tlmaxonly -multithreaded

Seems to work. Do you confirm dmsc ?

Yes, seems to work ok, with or without the $9B.

About direct binary output, you can use the "-b" option to minisim and if will skip the ATASCII to ASCII conversion:

Code:

./atarisim -b arlet-medium.65 | rng_test stdin8 -te 1 -tlmin 10 -tlmax 50 -tlmaxonly -multithreaded

Have Fun!

Top

Alex1

Post subject: Re: Random-number generation

Posted: Thu Apr 20, 2023 8:38 pm

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80

By the way, @dmsc i don't understand your code, you define :

Code:

state: .res 8

But how does it works? what are the init values for state? I suppose it will be random, it will use some free memory parts with random data inside to allocate the state ?

I use this code with fixed values :

Code:

.export start
ICPTL   = $0346
ICPTH   = $0347

        .zeropage
zp_start:
;state: .res 8
cnt:    .res    6
zp_end:

        .code

.proc   rand
; fast PRNG (pseudo random number generator) written in 6502 assembly language
; (C) Arlet Ottens 2023 <arlet@c-scape.nl>
; https://github.com/Arlet/pseudo-random-number-generator/blob/main/medium-6502.asm
    CLC
    LDA #$45
    ADC state+0
    STA state+0
    ADC state+1
    STA state+1
    ADC state+2
    STA state+2
    ADC state+3
    STA state+3
    ADC state+4
    STA state+4
    LDA state+5
    EOR state+7
    ADC state+4
    STA state+5
    ADC state+6
    STA state+6
    LDA state+7
    ASL
    ADC state+6
    STA state+7
    EOR state+2
    RTS
.endproc

state: .byte $FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF 

.proc print_hex_byte
        pha
        lsr
        lsr
        lsr
        lsr
        jsr     print_hex
        pla
print_hex:
        and     #$0F
        tax
        lda     hextab,x
        ; Fall through
::putc:
        ldx     #0
jump:   jmp     $FFFF

hextab: .byte   "0123456789ABCDEF"
.endproc


start:
        ; Init fast putchar
        lda     ICPTL
        clc
        adc     #1
        sta     print_hex_byte::jump+1
        lda     ICPTH
        adc     #0
        sta     print_hex_byte::jump+2
        ; Clear state
        ldx     #zp_end-zp_start-1
        lda     #0
zpclr:
        sta     zp_start, x
        dex
        bpl     zpclr

        ; Generate and print numbers
loop:
        jsr     rand
        jsr     print_hex_byte
       ; lda     #$9B
       ; jsr     putc

        inc     cnt
        bne     loop
        inc     cnt+1
        bne     loop
        inc     cnt+2
        bne     loop
        inc     cnt+3
        bne     loop
        inc     cnt+4
        bne     loop
        inc     cnt+5
        bne     loop
        rts

With state: .byte $FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF i've a problem with 1kb:

Quote:

length= 1 kilobyte (2^10 bytes), time= 2.1 seconds
Test Name Raw Processed Evaluation
FPF-14+6/64:all R= +17.3 p~= 7e-5 mildly suspicious
...and 15 test result(s) without anomalies

With state state: .byte $01,$00,$00,$00,$00,$00,$00,$00 , i've an unusual with 8 kb:

Quote:

length= 8 kilobytes (2^13 bytes), time= 6.8 seconds
Test Name Raw Processed Evaluation
[Low1/8]FPF-14+6/64:all R= +14.9 p~= 5e-4 unusual
...and 51 test result(s) without anomalies

With state: .byte $00,$00,$00,$00,$00,$00,$00,$01 , i've a FAIL with 1kb:

Quote:

length= 1 kilobyte (2^10 bytes), time= 1.2 seconds
Test Name Raw Processed Evaluation
FPF-14+6/64:all R= +33.5 p~= 4e-13 FAIL
...and 15 test result(s) without anomalies

With state state: .byte $01,$00,$00,$00,$00,$00,$00,$01 , i've an unusual with 64 kb:

Quote:

length= 64 kilobytes (2^16 bytes), time= 16.4 seconds
Test Name Raw Processed Evaluation
[Low1/8]Gap-16:B R= -3.3 p =1-1.0e-3 unusual
...and 90 test result(s) without anomalies

Could someone confirm this ?

Top

Page 12 of 17

[ 245 posts ]

Go to page Previous 1 ... 9, 10, 11, 12, 13, 14, 15 ... 17 Next

Board index » 6502.org Users Forum » Programming

All times are UTC

Who is online

Users browsing this forum: No registered users and 27 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum