Random-number generation

[Alex1]

With this code :

Code: Select all

.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 #$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 
.endproc

state: .byte $00,$00,$00,$00,$01

.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

I used :

Quote:

cl65 -tatari -Catari-asm.cfg arlet-minimal-binary.asm

Quote:

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

state: .byte $00,$00,$00,$00,$01

Quote:

length= 1 kilobyte (2^10 bytes), time= 1.2 seconds
Test Name Raw Processed Evaluation
DC6-5x4Bytes-1 R= +7.0 p = 4.0e-3 unusual
...and 15 test result(s) without anomalies

state: .byte $01,$00,$00,$00,$00

Quote:

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

state: .byte $00,$00,$00,$00,$01

Quote:

length= 1 kilobyte (2^10 bytes), time= 1.2 seconds
Test Name Raw Processed Evaluation
DC6-5x4Bytes-1 R= +7.0 p = 4.0e-3 unusual
...and 15 test result(s) without anomalies

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

Could someone confirm the problem ?

[Alex1]

With this code :

Quote:

.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- ... m-6502.asm
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
LDA s+2
ASL
ADC s+5
STA o+0
ADC s+3
STA o+1
ADC s+4
STA o+3
LDA o+2
ASL
ADC o+3
STA o+2
ADC o+0
STA o+0
ADC o+1
ASL
ADC o+0
STA o+1
ADC o+3
STA o+3
ADC o+2
ASL
ADC o+3
STA o+2
ADC o+1
STA o+1
ADC o+0
STA o+0
RTS
.endproc

s: .byte $00,$00,$00,$00,$01,$00
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
; 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

I used the Accumulator as random byte (s0)

compilation:

Quote:

cl65 -tatari -Catari-asm.cfg arlet-big-binary.asm

test:

Quote:

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

with s: .byte $00,$00,$00,$00,$01,$00

Quote:

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

length= 256 kilobytes (2^18 bytes), time= 25.6 seconds
Test Name Raw Processed Evaluation
[Low1/8]mod3n(0):(6,9-6) R= +11.5 p = 6.4e-5 unusual
...and 114 test result(s) without anomalies

with s: .byte $00,$01,$00,$00,$00,$00

Quote:

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

length= 512 kilobytes (2^19 bytes), time= 29.5 seconds
Test Name Raw Processed Evaluation
[Low1/8]DC6-6x2Bytes-1 R= +6.1 p = 1.8e-3 unusual
...and 128 test result(s) without anomalies

length= 2 megabytes (2^21 bytes), time= 43.0 seconds
Test Name Raw Processed Evaluation
[Low1/8]BCFN(0+2,13-8,T) R= +12.6 p = 4.2e-4 unusual
[Low1/8]DC6-9x1Bytes-1 R= +7.3 p = 5.3e-4 unusual
...and 154 test result(s) without anomalies

with s: .byte $00,$00,$00,$00,$00,$00

Quote:

length= 16 kilobytes (2^14 bytes), time= 9.7 seconds
Test Name Raw Processed Evaluation
[Low1/8]FPF-14+6/16:cross R= +5.5 p~= 5.9e-4 unusual
...and 61 test result(s) without anomalies

with s: .byte $00,$00,$00,$00,$00,$01

Quote:

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

rng=RNG_stdin8, seed=unknown
length= 2 kilobytes (2^11 bytes), time= 2.8 seconds
Test Name Raw Processed Evaluation
FPF-14+6/64:all R= +14.2 p~= 8e-4 unusual
...and 20 test result(s) without anomalies

length= 8 kilobytes (2^13 bytes), time= 6.3 seconds
Test Name Raw Processed Evaluation
FPF-14+6/16:all R= +10.3 p = 3.2e-5 mildly suspicious
[Low1/8]FPF-14+6/64:all R= +16.3 p~= 1e-4 unusual
...and 50 test result(s) without anomalies

with s: .byte $01,$00,$00,$00,$00,$01

Quote:

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

with s: .byte $01,$00,$00,$00,$00,$00

Quote:

length= 1 kilobyte (2^10 bytes), time= 1.3 seconds
Test Name Raw Processed Evaluation
DC6-9x1Bytes-1 R= +7.2 p = 7.0e-3 unusual
DC6-6x2Bytes-1 R= +6.4 p = 4.2e-3 unusual
...and 14 test result(s) without anomalies

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

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

with s: .byte $FF,$FF,$FF,$FF,$FF,$FF

Quote:

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

length= 4 megabytes (2^22 bytes), time= 57.1 seconds
Test Name Raw Processed Evaluation
DC6-9x1Bytes-1 R= -5.6 p =1-7.0e-4 unusual
...and 168 test result(s) without anomalies

Could someone confirm this ?

[Alex1]

I confirm the results with the C version of arlet-minimal and arlet-medium algorithm.

[dmsc]

Hi!

Alex1 wrote:

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

Code: Select all

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 ?

It is in the start procedure:

Code: Select all

        ; Clear state
        ldx     #zp_end-zp_start-1
        lda     #0
zpclr:
        sta     zp_start, x
        dex
        bpl     zpclr

There, all memory from "zp_start" up to "zp_end" is cleared to 0.

Have Fun!

[Alex1]

dmsc wrote:

There, all memory from "zp_start" up to "zp_end" is cleared to 0.

Oh yes thanks. So you test only with seed=0.

[Arlet]

Quote:

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

Please post your first 32 output bytes like this:

Code: Select all

./atarisim arlet-medium.65 | xxd -r -p | hexdump -C | head -2

[Alex1]

Arlet wrote:

Quote:

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

Please post your first 32 output bytes like this:

Code: Select all

./atarisim arlet-medium.65 | xxd -r -p | hexdump -C | head -2

Code: Select all

./atarisim -b arlet-medium-binary  | hexdump -C | head -2
00000000  0d 97 66 cf 80 fb ef 65  68 c5 9f 86 4c 04 7f 00  |..f....eh...L...|
00000010  f3 52 1a 3b d4 34 72 61  33 ee ac 09 87 8e 1e 02  |.R.;.4ra3.......|

Code: Select all

./atarisim arlet-medium-text | xxd -r -p | hexdump -C | head -2
00000000  0d 97 66 cf 80 fb ef 65  68 c5 9f 86 4c 04 7f 00  |..f....eh...L...|
00000010  f3 52 1a 3b d4 34 72 61  33 ee ac 09 87 8e 1e 02  |.R.;.4ra3.......|

[Arlet]

aha, I see the problem. It's caused by the addition of the -te1 -tlmin 10 arguments where you start testing randomness with only 1kB of data. With 2kB everything is fine. I think it's a limitation of the practrand code which was probably never intended to be run with such ridiculously small data sizes.

I can find seeds where chacha(8) also fails at 1 kB.

Code: Select all

% RNG_test 'chacha(8)' -seed 0x13c9d36c -te 1 -tlmin 10 -tlmax 10

RNG_test using PractRand version 0.95
RNG = chacha(8), seed = 0x13c9d36c
test set = expanded, folding = standard (32 bit)

rng=chacha(8), seed=0x13c9d36c
length= 1 kilobyte (2^10 bytes), time= 0.1 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/64:all                   R= +30.8  p~=   1e-11     FAIL           
  ...and 15 test result(s) without anomalies

[Alex1]

Arlet wrote:

aha, I see the problem. It's caused by the addition of the -te1 -tlmin 10 arguments where you start testing randomness with only 1kB of data. With 2kB everything is fine. I think it's a limitation of the practrand code which was probably never intended to be run with such ridiculously small data sizes.

Are you sure that it is not the other way around: Practrand is able to detect problems on small data sizes but not on large data sets, which would explain why there is never any error detected on large data sets when statistically there should be.
Because all the problems we are discovering now involve small sets given. It would be surprising if practrand's creator planned effective software on large data sets but not on small ones.
You said it tests all the data, but it seems likely that it doesn't and it only does random testing on large data sets. That's why it doesn't detect anything on large data sets.
Don't have any testing software other than Practrand?
Practrand seems frightening to me as to the quality of his results, one can doubt it.
Because as soon as a problem is detected you say "no but it's okay, I can find the same problem on another algorithm". The answer should be "ok I'll drop Practrand and I'll take something else".

Here are 3 random files generated with AES-128 CBC Mode.

All files pass the 1kb test without errors.

Quote:

cat 3.bin | rng_test stdin8 -te 1 -tlmin 10 -tlmax 50 -tlmaxonly -multithreaded
RNG_test using PractRand version 0.94
RNG = RNG_stdin8, seed = unknown
test set = expanded, folding = standard (8 bit)

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

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

random.7z

(6.55 KiB) Downloaded 85 times

[Arlet]

Alex1 wrote:

Here are 3 random files generated with AES-128 CBC Mode.

All files pass the 1kb test without errors.

Now try with 100 files.

[Alex1]

Arlet wrote:

Alex1 wrote:

Here are 3 random files generated with AES-128 CBC Mode.

All files pass the 1kb test without errors.

Now try with 100 files.

There you would like to do 100 tests of 1 kb on existing algorithms and compare the number of FAIL with yours? you think it's reliable as a method of testing a PRNG?
Because here you conclude that your algorithm is good only because other algorithms have the same errors (more errors, fewer errors?, we do not know): we cannot rely on errors to say "my algorithm is good".

[Arlet]

Quote:

There you would like to do 100 tests of 1 kb on existing algorithms and compare the number of FAIL with yours?

It's not a test of the algorithms, it's a test whether we can trust the verdict of PractRand for 1kB blocks.

Quote:

here you conclude that your algorithm is good only because other algorithms have the same errors

No, I conclude that the test isn't good enough if it finds errors in known good algorithms.

[Arlet]

It finds errors in /dev/random too:

Code: Select all

% RNG_test stdin8 -tlmin 10 -tlmax 10 -te 1 < /dev/random
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
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/64:all                   R= +36.0  p~=   1e-14     FAIL !         
  FPF-14+6/32:all                   R= +17.7  p~=   5e-5    mildly suspicious
  ...and 14 test result(s) without anomalies

[Alex1]

Arlet, you conclude that practrand is not good on 1 KB sets but there is no warning in the README file. If it's not good on 1kb why would it be good on a larger dataset.
We would have to find another tester than Practrand. He cannot be trusted. It's not clear if it's good on large data sets where it doesn't detect anything.

[BigEd]

It feels clear to me that testing the randomness of small chunks of data is more likely to come up with unusual situations.

If I make 10 coin tosses, the number of heads will vary from 5 by quite a bit, quite often. If I make 1000 coin tosses, the number of heads will vary from 500 by proportionally less.

A good randomness tester will show up more unusual situations in small blocks than a bad one. And a good random source may well come up with more unusual situations in small blocks than a bad one.