Page 11 of 17
Re: Random-number generation
Posted: Mon Apr 17, 2023 4:34 am
by Arlet
Can you publish the C version of your algorithm?
Yes i tried my algorithm with different seeds and no 'unusual' detected. Now it is at 4 TB and still no unusual.
Instead of letting a single seed run for a really long time, you should test it with short runs and more different seeds. If you already have 2TB of good data, and then you add another 256MB of unusual data, the average will still be good. If you had that same 256MB run by itself it would get reported.
If you toss a coin, and get 15 heads in a row, there's probably something wrong with the coin. If you toss a coin a billion times, and never get 15 heads in a row, there's probably also something wrong with the coin. Similarly, if you have a perfect random generator, and you examine short 256MB runs of output, some of them must be unusual. A 1-in-a-million event should happen 1 in a million times.
Re: Random-number generation
Posted: Mon Apr 17, 2023 7:39 am
by BigEd
It seems to me that we should also expect low probability events to happen sometimes. So those 'unusual' reports could be a positive sign, rather than a negative sign.
Re: Random-number generation
Posted: Mon Apr 17, 2023 8:25 am
by Arlet
Agreed, but since my minimal implementation starts to fail after a few GB, I would expect a somewhat higher rate of "unusual" reports after 256/512 MB than you would expect from a really good generator.
Re: Random-number generation
Posted: Mon Apr 17, 2023 2:26 pm
by Alex1
Arlet, after multiple other checks, I manage to reproduce the same "unusual" problem on my algorithm. So we can forget this problem, it's the same everywhere.
Re: Random-number generation
Posted: Mon Apr 17, 2023 5:42 pm
by IamRob
Somebody should ask ChatGPT how many iterations does it take for a random number to be truly random
or
How many random numbers it can generate before it starts repeating itself.
Re: Random-number generation
Posted: Mon Apr 17, 2023 6:36 pm
by Arlet
It's important to note that a truly random number cannot be determined by a set number of iterations. The concept of true randomness means that there is no pattern or predictability to the sequence of numbers generated.
One way to generate a random number is to use a random number generator (RNG) algorithm. RNG algorithms typically use a seed value to start the sequence of numbers and then use a complex mathematical formula to generate the subsequent numbers in the sequence. The randomness of the sequence is determined by the properties of the algorithm.
However, no RNG algorithm can generate truly random numbers as they are ultimately deterministic - given the same seed value and algorithm, the same sequence of numbers will always be generated. Therefore, the randomness of the numbers generated by an RNG algorithm can be evaluated statistically, but not determined by a set number of iterations.
To generate random numbers with a higher degree of randomness, researchers often use physical phenomena, such as thermal noise or radioactive decay, as sources of randomness. These methods are considered to produce true randomness as they are based on natural phenomena that are inherently unpredictable.
Re: Random-number generation
Posted: Tue Apr 18, 2023 1:38 am
by Arlet
I've just added a
better version for the 6502 to the github repository.. This version passed 8TB in PractRand (and is still going)
I've also added a C version for testing purposes.
Just like the minimal version, this code only produces 1 byte of output, but has improved randomness at the cost of some additional cycles.
Test output with all zero seed:
Code: Select all
00000000 00 7a ec 42 0d f3 4b e7 07 5d 28 e1 c0 0b ce f8 |.z.B..K..](.....|
00000010 79 00 43 37 7d 5a 0f 19 6c b3 8a f4 36 fa 00 bb |y.C7}Z..l...6...|
Re: Random-number generation
Posted: Tue Apr 18, 2023 2:02 pm
by dmsc
Hi!
I've just added a
better version for the 6502 to the github repository.. This version passed 4TB in PractRand (and is still going)
I've also added a C version for testing purposes.
Just like the minimal version, this code only produces 1 byte of output, but has improved randomness at the cost of some additional cycles.
Great RNG. I tested th 65-2 version with PractRand-0.95 in my simulator up to 64GB:
Code: Select all
~/Downloads/Math/random/algos/6502$ minisim arlet8-medium.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)
.... snip ....
rng=RNG_stdin8, seed=unknown
length= 32 gigabytes (2^35 bytes), time= 14206 seconds
no anomalies in 433 test result(s)
rng=RNG_stdin8, seed=unknown
length= 64 gigabytes (2^36 bytes), time= 27548 seconds
no anomalies in 448 test result(s)
IMHO, I would prefer a RNG with only 4 bytes of state and good speed, as I would never call it more than a few million times in any real 6502 program - so it would only need to pass PractRand up to 2^30 or so, but I know you are trading speed with state space here. 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.
The test code for your RNG runs in an Atari 8-bit computer and produces a string of hexadecimal numbers, the "conv8" program in the command line above converts it to raw 8-bit characters as input to PractRand:
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 #$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
.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
Have Fun!
Re: Random-number generation
Posted: Tue Apr 18, 2023 2:08 pm
by BigEd
I suspect the best tradeoff would be 5 bytes of state - enough to get 32 bit numbers out if you really need to. (Well, obviously not the best tradeoff, as that depends on all sorts of considerations! Perhaps what I mean to say is, I wonder how well one can do with just 5 bytes of state - 4 bytes not being enough for 32 bit purposes.)
Re: Random-number generation
Posted: Tue Apr 18, 2023 2:22 pm
by dmsc
Hi!
I suspect the best tradeoff would be 5 bytes of state - enough to get 32 bit numbers out if you really need to. (Well, obviously not the best tradeoff, as that depends on all sorts of considerations! Perhaps what I mean to say is, I wonder how well one can do with just 5 bytes of state - 4 bytes not being enough for 32 bit purposes.)
Not really, 4 bytes *is* good enough to get 32, 64 or 128 bits from the RNG, what it limits is the amount of different numbers that you could generate - for example, you would only get 2^32/4 32-bit numbers in the best case before the RNG starts to loop.
It is very simple to construct a slow RNG that takes 4 bit of state and generates perfectly good output, you just need to encrypt a counter with a good crypto algorithm, for example:
Code: Select all
function rng:
state = state + 1
return AES(state, "my arbitrary AES key")
This is exactly why LFSR generators are bad - they are simply counters with a different counting sequence. Saying that you can take the output to a non-linear permutation to generate good random numbers is the same as saying you can take a counter output to a non-linear permutation, and both will work.
Have Fun!
Re: Random-number generation
Posted: Tue Apr 18, 2023 2:41 pm
by BigEd
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.
Re: Random-number generation
Posted: Tue Apr 18, 2023 3:56 pm
by Arlet
The problem is that you'd want a random number generator that doesn't have short loops for bad seeds. It's not too difficult to create a chaotic function that maps 32->32 bits, and that you can call repeatedly to create good random numbers. However, it's very likely that such a function will have some bad seeds where it has a short loop, or even a fixpoint where f(x) = x for some value.
There are a few ways to create a function that will go through every value before cycling, but none of these functions produce excellent random numbers. The
LCG comes closest, but the LSB is very poor (also, the wide multiply does not suit the 6502 very well). A solution is to build the random generator out of 2 parts. An iterator part that goes through entire state, and then an output function that improves the randomness.
Now, the problem on the 6502 is that you can only do arithmetic operations on the accumulator, so there's very little you can do to create the output function. You really need some temporary variables to mix things around properly. But if you add some temporary values, you might as well make them part of the state. That's how I ended up with 8 bytes of state. Note that only 5 of those bytes are guaranteed to go through all states, and the remaining 3 are used as an output function with feedback.
Re: Random-number generation
Posted: Tue Apr 18, 2023 4:03 pm
by Arlet
so it would only need to pass PractRand up to 2^30
The
minimal 6502 implementation I have on github does close to what you want. It's a little better. Its period is guaranteed to be at least 4GB. It might be possible to remove 1 or 2 instructions to make it even shorter for a small drop in quality.
Re: Random-number generation
Posted: Tue Apr 18, 2023 4:52 pm
by Alex1
Hi!
Great RNG. I tested th 65-2 version with PractRand-0.95 in my simulator up to 64GB:
Is there a link to download this simulator "minisim" ?
Re: Random-number generation
Posted: Tue Apr 18, 2023 8:07 pm
by dmsc
Hi!
Hi!
Great RNG. I tested the 6502 version with PractRand-0.95 in my simulator up to 64GB:
Is there a link to download this simulator "minisim" ?
It is a "command line" Atari 8-bit simulator:
https://github.com/dmsc/mini65-sim
Have Fun!