Page 13 of 17
Re: Random-number generation
Posted: Thu Apr 20, 2023 9:24 pm
by 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
cl65 -tatari -Catari-asm.cfg arlet-minimal-binary.asm
./atarisim -b arlet-minimal-binary | rng_test stdin8 -te 1 -tlmin 10 -tlmax 50 -tlmaxonly -multithreaded
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= 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
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
Re: Random-number generation
Posted: Thu Apr 20, 2023 9:48 pm
by Alex1
With this 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- ... 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
cl65 -tatari -Catari-asm.cfg arlet-big-binary.asm
./atarisim -b arlet-big-binary | rng_test stdin8 -te 1 -tlmin 10 -tlmax 50 -tlmaxonly -multithreaded
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
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
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
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
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
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
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 ?
Re: Random-number generation
Posted: Thu Apr 20, 2023 10:32 pm
by Alex1
I confirm the results with the C version of arlet-minimal and arlet-medium algorithm.
Re: Random-number generation
Posted: Thu Apr 20, 2023 11:12 pm
by dmsc
Hi!
By the way, @dmsc i don't understand your code, you define :
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!
Re: Random-number generation
Posted: Thu Apr 20, 2023 11:47 pm
by Alex1
There, all memory from "zp_start" up to "zp_end" is cleared to 0.
Oh yes thanks. So you test only with seed=0.
Re: Random-number generation
Posted: Thu Apr 20, 2023 11:54 pm
by Arlet
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
Re: Random-number generation
Posted: Thu Apr 20, 2023 11:59 pm
by Alex1
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.......|
Re: Random-number generation
Posted: Fri Apr 21, 2023 5:23 am
by 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
Re: Random-number generation
Posted: Fri Apr 21, 2023 1:00 pm
by Alex1
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.
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)
Re: Random-number generation
Posted: Fri Apr 21, 2023 3:36 pm
by Arlet
Here are 3 random files generated with AES-128 CBC Mode.
All files pass the 1kb test without errors.
Now try with 100 files.
Re: Random-number generation
Posted: Fri Apr 21, 2023 3:42 pm
by Alex1
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".
Re: Random-number generation
Posted: Fri Apr 21, 2023 3:58 pm
by Arlet
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.
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.
Re: Random-number generation
Posted: Fri Apr 21, 2023 4:01 pm
by 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
Re: Random-number generation
Posted: Fri Apr 21, 2023 6:51 pm
by 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.
Re: Random-number generation
Posted: Fri Apr 21, 2023 8:22 pm
by 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.