Random-number generation

[Arlet]

Quote:

I have a huge choice of 12 cycle sequences, and it's not very likely that this (admittedly clever) sequence is optimal for the purpose of mixing bits randomly.

Specifically, I think that a simple 4x ROL instruction sequence would work equally well, as long as we treat the C flag as part of the random state. But if you're going to use 4x ROL, there's no need to artificially constrain yourself by putting them in a strict sequence.

Now, if we were able to do a nibble swap in 2 or 3 cycles, it would have been a different matter.

[BigDumbDinosaur]

barrym95838 wrote:

Arlet wrote:

Unfortunately, doing a nibble swap on 6502 is quite expensive, and probably not really worth it.

http://6502.org/source/general/SWN.html
Eight bytes and 12 cycles, so not terrible. Depends on your definition of "expensive", I suppose.

I don’t see an issue with the apparent “expense” of the linked nybble swap. If performance truly is a concern, then it’s time to crank up the clock speed or use the 65C816 and rewrite the code to do byte-swaps in a word for a potentially better effect on quality. The 816’s XBA instruction only takes three cycles. Jus’ sayin’

[Arlet]

BigDumbDinosaur wrote:

I don’t see an issue with the apparent “expense” of the linked nybble swap. If performance truly is a concern, then it’s time to crank up the clock speed or use the 65C816 and rewrite the code to do byte-swaps in a word for a potentially better effect on quality.

The challenge of the project is to create a random generator that produces good quality randomness in a minimal amount of cycles, for a particular target (in my case the 6502). A nibble swap is a potentially useful primitive, because it helps to spread the randomness between upper and lower bits. The weak part of my random generator structure is the residual regularity in the lower bits, so mixing them with upper bits would improve the result.

A 12 cycle nibble swap being "too expensive" is not absolute. It simply means that the same goal (good quality randomness) can be better achieved with a different sequence of instructions that take fewer than 12 cycles. Performance is not a concern. There are no requirements. It's simply a fun challenge to produce a certain result in minimum number of cycles, that may be useful to some people. Part of the challenge is to work within the limitations of the chosen target.

[Alex1]

Quote:

It's simply a fun challenge to produce a certain result in minimum number of cycles, that may be useful to some people. Part of the challenge is to work within the limitations of the chosen target.

Ok if the challenge is to use the minimum number of cycles, i notice that Arlet's last algorithm is 104 cycles (for the main part) :

Code: Select all

2      clc
2	lda #$45
4	adc s+0
4	sta s+0
4	adc s+1
4	sta s+1
4	adc s+2
4	sta s+2
4	adc s+3
4	sta s+3
4	adc s+4
4	sta s+4
4	adc s+5
4	sta s+5
4	adc s+3
4	sta o+0 
4	adc s+6
2	asl a  
4	sta s+6
4	adc s+2
4	sta o+1 
4	adc s+6
2	asl a   
4	sta s+6
4	adc s+4
4	sta o+2 
4	adc s+5
4	sta o+3 
	
104	

[Alex1]

Here is my 1995 PRNG code :

call Init: one time
each time you want a random byte, call begin:
the random byte is in rndbyte.

The period before repetition is factorial 256 : !(256)

Code: Select all

//  Random Generator 1995

//----------------------------------------------------
// 			Main Program
//----------------------------------------------------

init:
    ldx #0
    stx storex
    stx storey
loop:
    lda array1,x
    sta array,x
    inx
    bne loop
    rts

begin:
    ldx storex
    inx
    lda array,x
    pha
    clc
    adc storey
    sta storey
    ldy storey
    lda array,y
    sta array,x
    pla
    sta array,y
    clc
    adc array,x
    stx storex
    tax
    lda array,x
    sta rndbyte
    rts

storex: .byte $00
storey: .byte $00
rndbyte: .byte $00
array: .byte 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
array1: .byte  85,40,23,156,235,170,177,134,56,192,69,86,100,230,141,164,109,218,155,97,144,132,117,130,37,153,6,0,129,43,175,187,53,16,71,160,244,173,202,176,229,34,105,92,248,77,14,119,126,242,169,17,213,158,201,165,101,57,46,78,231,253,13,237,120,111,221,58,54,197,210,133,114,42,110,118,48,50,240,36,123,190,74,139,25,135,196,191,59,84,89,255,226,161,62,205,146,232,172,157,182,224,24,72,20,174,168,95,102,15,140,233,211,108,239,44,219,107,112,149,125,9,220,186,223,147,96,238,104,33,3,193,116,18,208,38,52,41,188,87,70,8,7,83,142,27,79,121,179,152,166,145,93,189,99,67,234,136,198,90,216,51,63,251,206,98,209,204,73,200,91,115,183,5,138,181,131,167,113,254,31,243,246,150,137,76,203,4,245,49,11,21,252,94,39,128,212,80,60,30,1,236,28,103,185,66,214,82,64,61,12,249,55,47,215,2,22,75,81,29,171,154,250,68,178,127,32,162,222,159,35,19,26,227,199,225,184,45,195,10,148,106,88,194,217,207,180,163,151,124,228,143,241,247,122,65

[Alex1]

The main part is only 65 cycles. Did I win the fun challenge?

Code: Select all

ldx storex   -- 4 cycles
inx	          -- 2 cycles
lda array,x  -- 5 cycles
pha	           -- 3 cycles 
clc	           -- 2 cycles 
adc storey  -- 4 cycles 
sta storey  -- 4 cycles 
ldy storey  -- 4 cycles
lda array,y -- 5 cycles
sta array,x -- 5 cycles 
pla	    -- 4 cycles 
sta array,y -- 5 cycles 
clc	    -- 2 cycles
adc array,x -- 5 cycles 
stx storex  -- 4 cycles 
tax	    -- 2 cycles 
lda array,x -- 5 cycles 

65 cycles

[Alex1]

The atarisim code is :

It can be compiled with :

Quote:

cl65 -tatari -Catari-asm.cfg 1995prng.asm

and can be run with :

Quote:

./atarisim 1995prng | xxd -r -p | rng_test stdin8

Code: Select all

.export start
ICPTL   = $0346
ICPTH   = $0347

        .zeropage
zp_start:
cnt:    .res    6
zp_end:

        .code

.proc   init
                
init:
    ldx #0
    stx storex
    stx storey
loop:
    lda array1,x
    sta array,x
    inx
    bne loop
    rts
.endproc

.proc   begin
    ldx storex
    inx
    lda array,x
    pha
    clc
    adc storey
    sta storey
    ldy storey
    lda array,y
    sta array,x
    pla
    sta array,y
    clc
    adc array,x
    stx storex
    tax
    lda array,x
    sta rndbyte
    rts
.endproc

storex: .byte $00
storey: .byte $00
rndbyte: .byte $00
array: .byte 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
array1: .byte  85,40,23,156,235,170,177,134,56,192,69,86,100,230,141,164,109,218,155,97,144,132,117,130,37,153,6,0,129,43,175,187,53,16,71,160,244,173,202,176,229,34,105,92,248,77,14,119,126,242,169,17,213,158,201,165,101,57,46,78,231,253,13,237,120,111,221,58,54,197,210,133,114,42,110,118,48,50,240,36,123,190,74,139,25,135,196,191,59,84,89,255,226,161,62,205,146,232,172,157,182,224,24,72,20,174,168,95,102,15,140,233,211,108,239,44,219,107,112,149,125,9,220,186,223,147,96,238,104,33,3,193,116,18,208,38,52,41,188,87,70,8,7,83,142,27,79,121,179,152,166,145,93,189,99,67,234,136,198,90,216,51,63,251,206,98,209,204,73,200,91,115,183,5,138,181,131,167,113,254,31,243,246,150,137,76,203,4,245,49,11,21,252,94,39,128,212,80,60,30,1,236,28,103,185,66,214,82,64,61,12,249,55,47,215,2,22,75,81,29,171,154,250,68,178,127,32,162,222,159,35,19,26,227,199,225,184,45,195,10,148,106,88,194,217,207,180,163,151,124,228,143,241,247,122,65



.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
        jsr     init
        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     begin
        lda     rndbyte
        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

[teamtempest]

Code: Select all

init:
    ldx #0
    ldy #0
    stx storex
    stx storey
    rts

begin:
    ldx storex
    inx
    lda array,x
    pha
    clc
    adc storey
    sta storey
    ldy storey
    lda array,y
    sta array,x
    pla
    sta array,y
    clc
    adc array,x
    stx storex
    tax
    lda array,x
    sta rndbyte
    rts

storex: .byte $00
storey: .byte $00
rndbyte: .byte $00

I'm curious why you need the 'init' procedure at all. The values in 'storex' and 'storey' are fixed at assembly time, and the values do not change thereafter. You apparently do nothing with the return value from 'init' (which only loads the Y-register and then does nothing with it. Is that intentional?).

If 'storex' and 'storey' were arbitrary uninitialized RAM locations, then yes, an 'init' of some sort would be necessary. But even then you could call 'init' once (taking care to actually store the Y-register if a non-zero seed is used) and fall through to 'begin', and that would be your first iteration. After that always call 'begin', just like now.

[Alex1]

teamtempest wrote:

I'm curious why you need the 'init' procedure at all. The values in 'storex' and 'storey' are fixed at assembly time, and the values do not change thereafter. You apparently do nothing with the return value from 'init' (which only loads the Y-register and then does nothing with it. Is that intentional?).

Oh yes thanks, it was a mistake. I modified the code (but that changes nothing to the algorithm).
All my old 6502 codes are on paper and I have to type them again on the computer to revive them. I made a copying error. The paper code was :

Code: Select all

    ldx #0
    ldy #0
    stx storex
    sty storey

But the ldy is useless, because in this challenge every cycle counts, we intend to remove it and stay like this:

Code: Select all

    ldx #0
    stx storex
    stx storey

The init: function is used to reset the algorithm. If I want to go back to the beginning and get the same random byte string, just make a call to init:. Without this initialization function, once the algorithm is launched, I can't start over at the beginning.
In addition I no longer have the assembler I was using when the code was written. I need to modify the code to work with my current assembler. For example, it does not accept this:

Code: Select all

storex:    .res    1
storey:    .res    1

[Arlet]

Alex1 wrote:

The main part is only 65 cycles. Did I win the fun challenge?

Not quite. My code produces 32 bits at a time, and it's only 80 cycles when you put all the variables in zero page, so that's 20 cycles/byte. On the other hand, the random quality of my output is considerably lower. For a real apples-to-apples comparison, we would have to define some categories regarding output quality (and how to test that), memory footprint, as well as the number of output bits.

By the way, if I'm not mistaken, then this is an implementation of RC4

[Arlet]

Alex1 wrote:

If I want to go back to the beginning and get the same random byte string, just make a call to init:. Without this initialization function, once the algorithm is launched, I can't start over at the beginning.

Shouldn't you also restore your 'array' contents ?

[Alex1]

Arlet wrote:

Alex1 wrote:

If I want to go back to the beginning and get the same random byte string, just make a call to init:. Without this initialization function, once the algorithm is launched, I can't start over at the beginning.

Shouldn't you also restore your 'array' contents ?

Indeed, corrected !

[Alex1]

Arlet wrote:

Alex1 wrote:

The main part is only 65 cycles. Did I win the fun challenge?

Not quite. My code produces 32 bits at a time, and it's only 80 cycles when you put all the variables in zero page, so that's 20 cycles/byte. On the other hand, the random quality of my output is considerably lower. For a real apples-to-apples comparison, we would have to define some categories regarding output quality (and how to test that), memory footprint, as well as the number of output bits.

By the way, if I'm not mistaken, then this is an implementation of RC4

Yes you are right, it's ARC4. The other name is a trademark. The code was published in 1994 on the newsgroups where I was an avid reader. The following year I programmed it in 6502. It's my code but not my algorithm, that's why I didn't put my name in it. Just like LFSR, I always use algorithms based on strong math.

Quote:

For a real apples-to-apples comparison, we would have to define some categories regarding output quality (and how to test that), memory footprint, as well as the number of output bits.

I offered you to find another software than Practrand that would be better on large amounts of data. I don't think you found one and neither did I. Thus, for this fun challenge, we can stay on Practrand's results to know if an algorithm succeeds in the challenge or not

If I did not make a mistake (which is always possible) I am ahead of you in the challenge because your algorithm does not meet the characteristics:

You said that your last algorithm produces 2^48 bytes before looping, that's not what Practrand says.

Quote:

Nice 32 bit random generator, with 7 bytes of state, and 4 bytes of output. Period is guaranteed to be at least 2^48 words, so for all practical purposes will never repeat.

My algorithms LFSR64+LCG64 or ARC4 remain random throughout the period because they are based on strong maths.

Here is my code, here are the results with only the o+3 output:

Code: Select all

.export start
ICPTL   = $0346
ICPTH   = $0347

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

        .code

.proc   rand
    CLC
    LDA #$45
    ADC s+0
    STA s+0
    ADC s+1
    STA s+1
    ADC s+2
    STA s+2
    ADC s+3
    STA s+3
    ADC s+4
    STA s+4
    ADC s+5
    STA s+5
    ADC s+3
    STA o+0 
    ADC s+6
    ASL A
    STA s+6
    ADC s+2
    STA o+1 
    ADC s+6
    ASL A
    STA s+6
    ADC s+4
    STA o+2 
    ADC s+5
    STA o+3 
    RTS
.endproc

s: .byte $FF,$FF,$FF,$FF,$FF,$FF, $FF
o: .byte $00,$00,$00,$00
.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
    ;    lda     o+0
    ;    jsr     print_hex_byte
    ;    lda     o+1
    ;    jsr     print_hex_byte
    ;    lda     o+2
        jsr     print_hex_byte
        lda     o+3
        jsr     print_hex_byte
        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

Quote:

./atarisim arlet-new | xxd -r -p | ./rng_test stdin8
RNG_test using PractRand version 0.94
RNG = RNG_stdin8, seed = unknown
test set = core, folding = standard (8 bit)

rng=RNG_stdin8, seed=unknown
length= 2 megabytes (2^21 bytes), time= 3.6 seconds
no anomalies in 63 test result(s)

rng=RNG_stdin8, seed=unknown
length= 4 megabytes (2^22 bytes), time= 7.8 seconds
no anomalies in 71 test result(s)

rng=RNG_stdin8, seed=unknown
length= 8 megabytes (2^23 bytes), time= 15.9 seconds
no anomalies in 76 test result(s)

rng=RNG_stdin8, seed=unknown
length= 16 megabytes (2^24 bytes), time= 31.7 seconds
no anomalies in 84 test result(s)

rng=RNG_stdin8, seed=unknown
length= 32 megabytes (2^25 bytes), time= 61.5 seconds
no anomalies in 93 test result(s)

rng=RNG_stdin8, seed=unknown
length= 64 megabytes (2^26 bytes), time= 121 seconds
no anomalies in 99 test result(s)

rng=RNG_stdin8, seed=unknown
length= 128 megabytes (2^27 bytes), time= 239 seconds
no anomalies in 108 test result(s)

rng=RNG_stdin8, seed=unknown
length= 256 megabytes (2^28 bytes), time= 474 seconds
no anomalies in 118 test result(s)

rng=RNG_stdin8, seed=unknown
length= 512 megabytes (2^29 bytes), time= 943 seconds
no anomalies in 126 test result(s)

rng=RNG_stdin8, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 1874 seconds
no anomalies in 135 test result(s)

rng=RNG_stdin8, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 3744 seconds
Test Name Raw Processed Evaluation
TMFn(2+6):wl R= +21.8 p~= 1e-6 mildly suspicious
...and 143 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 4 gigabytes (2^32 bytes), time= 7461 seconds
Test Name Raw Processed Evaluation
TMFn(2+5):wl R= +35.9 p~= 1e-14 FAIL
TMFn(2+6):wl R= +48.5 p~= 4e-22 FAIL !!
TMFn(2+7):wl R= +18.4 p~= 3e-5 unusual
...and 148 test result(s) without anomalies

With o+0, o+1, o+2, o+3 :

Code: Select all

        ; Generate and print numbers
loop:
        jsr     rand
        lda     o+0
        jsr     print_hex_byte
        lda     o+1
        jsr     print_hex_byte
        lda     o+2
        jsr     print_hex_byte
        lda     o+3
        jsr     print_hex_byte

Quote:

./atarisim arlet-new | xxd -r -p | ./rng_test stdin8
RNG_test using PractRand version 0.94
RNG = RNG_stdin8, seed = unknown
test set = core, folding = standard (8 bit)

rng=RNG_stdin8, seed=unknown
length= 2 megabytes (2^21 bytes), time= 2.1 seconds
no anomalies in 63 test result(s)

rng=RNG_stdin8, seed=unknown
length= 4 megabytes (2^22 bytes), time= 4.9 seconds
no anomalies in 71 test result(s)

rng=RNG_stdin8, seed=unknown
length= 8 megabytes (2^23 bytes), time= 9.8 seconds
no anomalies in 76 test result(s)

rng=RNG_stdin8, seed=unknown
length= 16 megabytes (2^24 bytes), time= 19.3 seconds
no anomalies in 84 test result(s)

rng=RNG_stdin8, seed=unknown
length= 32 megabytes (2^25 bytes), time= 36.3 seconds
Test Name Raw Processed Evaluation
TMFn(2+0):wl R= +69.0 p~= 1e-34 FAIL !!!
...and 92 test result(s) without anomalies

[Arlet]

Alex1 wrote:

You said that your last algorithm produces 2^48 bytes before looping, that's not what Practrand says. Here is my code, here are the results with only the o+3 output

It's not looping, though. It fails random tests before looping. Imagine you have a simple 64 bit counter, it wouldn't be random, but it would still produce 2^64 unique outputs before looping.

ARC4 is a good random generator, but for average 6502 systems, the 256 byte RAM array is relatively expensive.

I will accept the challenge though, but then I'm also going to use a 256 byte RAM, and 8 bit output. What kind of performance are we looking for ? I don't mind trying for 32TB passing on PractRand, but it will take a really long time to run such tests. I don't really want to hog my PC for 3 months testing various algorithms. Will you accept 1TB, and plain "stdin8" ?

[Alex1]

Arlet wrote:

It's not looping, though. It fails random tests before looping. Imagine you have a simple 64 bit counter, it wouldn't be random, but it would still produce 2^64 unique outputs before looping.

My algorithms LFSR64+LCG64 or ARC4 remain random throughout the period because they are based on strong maths.
When I announce a period for my algorithms, they remain random throughout the period. You have to do the same otherwise it's cheating for the challenge I too can create an algorithm with a period of 2^1024 but which will only be random on 100 KB

Quote:

I will accept the challenge though, but then I'm also going to use a 256 byte RAM, and 8 bit output. What kind of performance are we looking for ? I don't mind trying for 32TB passing on PractRand, but it will take a really long time to run such tests. I don't really want to hog my PC for 3 months testing various algorithms. Will you accept 1TB, and plain "stdin8" ?

I let my Raspberry PI (only one core used) run for 70 days to prove that my LFSR64 + LCG64 passed the 16 TB, 1TB seems to me very little to prove that an algorithm is random. Time is not an issue, just use a system that can stay on for a long time because it does something else in the meantime. In a challenge, everyone must prove their claims. Here it is up to me to prove that your algorithm is not random, I doubled the work

Code: Select all

rng=RNG_stdin8, seed=unknown
length= 16 terabytes (2^44 bytes), time= 6061817 seconds
no anomalies in 225 test result(s)