As I said in a previous message, LFSR are building blocks. So are LCG.
The miracle is that if we mix the output of an LFSR and the output of an LCG, it passes ALL statistical tests :
even PractRand. And mathematically we know that it will give 2^64 random bits.
First a 8-bytes seed must be put at
seed:The seed can vary from 0 to $FFFFFFFFFFFFFFFF.
And a 8-bytes seed must be put at
seedlfsr:The seed can vary from 1 to $FFFFFFFFFFFFFFFF but never 0 otherwise the LFSR produces only bits to 0.
Each call to the
begin: function returns a pseudorandom byte in
rndbyte:First
init: must be call one time.
After
begin: must be call for each generated byte (
rndbyte:) that can be use directly.
The test vector is :For a
seedlfsr = $FFFFFFFFFFFFFFFF
adn
seed = $FFFFFFFFFFFFFFFF
the first 50 bytes are :Quote:
72 BB 94 D2 AD 1D 2D 21 97 4B DF 5A 06 A5 38 C1 67 75 5D F6 29 DC 95 15 77 C5 38 0E 3B B3 20 1C ED EA 6A 76 79 AB 73 97 18 FA F8 A5 AD 0F E2 26 EC 74
Code:
// Pukall LFSR 64 + Pukall LCG 64
//----------------------------------------------------
// Main Program
//----------------------------------------------------
init:
jsr initlfsr
jsr initlcg
rts
begin:
jsr startlfsr
jsr beginlcg
lda rndbytelfsr
clc
adc rndbyte
sta rndbyte
rts
initlfsr:
ldx #0
looplfsr:
jsr startlfsr
inx
cpx #64
bne looplfsr
rts
startlfsr:
lda #$00
sta rndbytelfsr
lda #$01
sta mask
beginlfsr:
asl seedlfsr
rol seedlfsr+1
rol seedlfsr+2
rol seedlfsr+3
rol seedlfsr+4
rol seedlfsr+5
rol seedlfsr+6
rol seedlfsr+7
bcc notlfsr
lda seedlfsr
eor #$01
sta seedlfsr
lda seedlfsr+7
eor #$B0
sta seedlfsr+7
lda rndbytelfsr
ora mask
sta rndbytelfsr
notlfsr:
asl mask
bcc beginlfsr
rts
initlcg:
lda #6
sta pos
rts
beginlcg:
ldx pos
cpx #6
bne rnd
jsr start
ldx #0
clc
php
loop0:
lda seed,x
plp
adc dda,x
php
sta seed,x
inx
cpx #8
bne loop0
plp
rnd:
ldx pos
lda seed,x
sta rndbyte
dex
cpx #2
bne end2
end:
lda #6
sta pos
rts
end2:
stx pos
rts
start:
lda #0
ldx #15
loop:
sta result,x
dex
cpx #7
bne loop
ldy #64
part1:
sty storey
ldx #7
lsr seed,x
php
dex
loop1:
plp
ror seed,x
php
dex
cpx #0
bne loop1
plp
ror seed
bcc part2
ldx #7
ldy #0
clc
php
loop2:
inx
lda result,x
plp
adc two,y
php
sta result,x
iny
cpy #8
bne loop2
plp
part2:
ror
php
ldx #15
sta result,x
loop3:
dex
plp
ror result,x
php
cpx #0
bne loop3
plp
ldy storey
dey
bne jump
ldx #0
loop4:
lda result,x
sta seed,x
inx
cpx #8
bne loop4
rts
jump:
jmp part1
seed: .byte $FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF
rndbyte: .byte $FF
result: .byte $FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF
two: .byte $2D,$7F,$95,$4C,$2D,$F4,$51,$58
dda: .byte $01,$00,$00,$00,$00,$00,$00,$00
storey: .byte $FF
pos: .byte $FF
seedlfsr: .byte $FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF
mask: .byte $00
rndbytelfsr: .byte $00
PRACTRAND tests :Code:
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= 8 megabytes (2^23 bytes), time= 3.7 seconds
no anomalies in 76 test result(s)
rng=RNG_stdin8, seed=unknown
length= 16 megabytes (2^24 bytes), time= 8.4 seconds
no anomalies in 84 test result(s)
rng=RNG_stdin8, seed=unknown
length= 32 megabytes (2^25 bytes), time= 17.0 seconds
no anomalies in 93 test result(s)
rng=RNG_stdin8, seed=unknown
length= 64 megabytes (2^26 bytes), time= 32.5 seconds
no anomalies in 99 test result(s)
rng=RNG_stdin8, seed=unknown
length= 128 megabytes (2^27 bytes), time= 62.7 seconds
no anomalies in 108 test result(s)
rng=RNG_stdin8, seed=unknown
length= 256 megabytes (2^28 bytes), time= 121 seconds
no anomalies in 118 test result(s)
rng=RNG_stdin8, seed=unknown
length= 512 megabytes (2^29 bytes), time= 237 seconds
no anomalies in 126 test result(s)
rng=RNG_stdin8, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 470 seconds
no anomalies in 135 test result(s)
rng=RNG_stdin8, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 936 seconds
no anomalies in 144 test result(s)
rng=RNG_stdin8, seed=unknown
length= 4 gigabytes (2^32 bytes), time= 1846 seconds
no anomalies in 151 test result(s)
rng=RNG_stdin8, seed=unknown
length= 8 gigabytes (2^33 bytes), time= 3662 seconds
no anomalies in 159 test result(s)
rng=RNG_stdin8, seed=unknown
length= 16 gigabytes (2^34 bytes), time= 7278 seconds
no anomalies in 167 test result(s)
rng=RNG_stdin8, seed=unknown
length= 32 gigabytes (2^35 bytes), time= 14372 seconds
no anomalies in 173 test result(s)
rng=RNG_stdin8, seed=unknown
length= 64 gigabytes (2^36 bytes), time= 28416 seconds
no anomalies in 181 test result(s)
rng=RNG_stdin8, seed=unknown
length= 128 gigabytes (2^37 bytes), time= 55896 seconds
no anomalies in 189 test result(s)
rng=RNG_stdin8, seed=unknown
length= 256 gigabytes (2^38 bytes), time= 110189 seconds
no anomalies in 195 test result(s)
rng=RNG_stdin8, seed=unknown
length= 512 gigabytes (2^39 bytes), time= 208856 seconds
no anomalies in 202 test result(s)
rng=RNG_stdin8, seed=unknown
length= 1 terabyte (2^40 bytes), time= 369656 seconds
no anomalies in 208 test result(s)
rng=RNG_stdin8, seed=unknown
length= 2 terabytes (2^41 bytes), time= 686317 seconds
no anomalies in 213 test result(s)
Login
Register
FAQ
Search
