tiny pseudo random generator
category: code [glöplog]
give your tips and tricks for tiny prng here.
random number is now in al or ah.
no need for seed. the seed is integrated in the function. what does this mean? the "inc al" instruction increments al and acts as a seed on each iteration.
First instances of 'al' and 'ah' will be different (0 and 128), but the consecutive numbers will be the same.
Random numbers are:
Different effects can be used for instance if rotating by other numbers ror, x etc.. where x Є {1..8}. "inc al" can also be changed to "add al, x".
Periodicity of this prng is 14313 for ror,1 and inc. This changes if using other numbers.
Code:
inc al
xor al, ah
ror al, 1
xchg ah, alrandom number is now in al or ah.
no need for seed. the seed is integrated in the function. what does this mean? the "inc al" instruction increments al and acts as a seed on each iteration.
First instances of 'al' and 'ah' will be different (0 and 128), but the consecutive numbers will be the same.
Random numbers are:
Code:
0/128,192,160,176,136,156,138,139,0,70,163,114,107,12,48,158,215,36,126,173,105,227,...Different effects can be used for instance if rotating by other numbers ror, x etc.. where x Є {1..8}. "inc al" can also be changed to "add al, x".
Periodicity of this prng is 14313 for ror,1 and inc. This changes if using other numbers.
7
;;random:
;;;R1:LD C,$18
;;R2:LD A,#70
;;R1: ADD A,$15:LD C,A;r1
;; LD (R1+1),A
;;R3:LD A,#FD
;; SUB C:LD C,A,(R2+1),A
;; RRCA:LD (R3+1),A
;; RET
;;;R1:LD C,$18
;;R2:LD A,#70
;;R1: ADD A,$15:LD C,A;r1
;; LD (R1+1),A
;;R3:LD A,#FD
;; SUB C:LD C,A,(R2+1),A
;; RRCA:LD (R3+1),A
;; RET
This is an honest Galois-type LSFR for Z80:
The SEED is stored in a 16-bit register IX (could also be IY or HL).
As long as the starting value of the SEED is non-zero, you get the full 65535 period for all three values specified there.
Code:
add ix, ix
sbc a
and #BD ; instead of #BD, one can use #3F or #D7
xor ixl
ld ixl, aThe SEED is stored in a 16-bit register IX (could also be IY or HL).
As long as the starting value of the SEED is non-zero, you get the full 65535 period for all three values specified there.
introspec: very good. did you use that in BB? btw, BB is very kewl.
No, I did not, it needed better PRNG. To cut the long story short, a while ago I brute-forced all 16 and 24 bit Galous-type LSFRs, based on few types of polynomials that I knew could be efficiently implemented on Z80. BB uses the following 24-bit LSFR:
BB uses feedback constant #1B and a slightly different form of code, which is clumsier than this.
Code:
ld a, c
add ix, ix
rla
ld c, a
sbc a
and #DB ; instead of #DB you can use #B1, #F5, #1B, #DB or #87
xor ixl
ld ixl, aBB uses feedback constant #1B and a slightly different form of code, which is clumsier than this.
introspec: ok. i see. hope you one day can explain to me how you did those brute-force techniques and xor-algorithms in the intro. I know you said it was easy when you explained it in the thread of the release, but I blew it after some attempts on my own. So I must have missed something. have tou any email i can reach you on? I can ask you there on my next try.
I had some ideas, and implemented some brownian motion like in mona but with more parameters, need some brute-force tehcnique for this.
I had some ideas, and implemented some brownian motion like in mona but with more parameters, need some brute-force tehcnique for this.
rudi, yes, not a problem, just write to zxintrospec@gmail.com and I'll be happy to help.
introspec: thank you
old chestnut for c64, you a) lose a sid voice and b) sometimes get same number if read twice on same frame but meh
Code:
lda #$81 ; set noise waveform channel 3
sta $d412
lda #$ff ; set fastest pitch freq channel 3
sta $d40f
lda $d41b ; give me a number with channel 3 sid read
Code:
lodsw
(drops mic)
@trixter :D
let me start with the thread i already wrote : HERE
there is a funny and strange relation between fractals and really really good random number generators. i did not (yet) prove or publish what i found, but here is the core routine, displaying what the algorithm generates when it's "forced" to generate a series of ones and zeros.
result:
compare it with the pictures of https://www.random.org/analysis/
good:
bad:
i would still have to run this thingy through all hard statistical tests, and enhance it to 32 or 64bits.
The real core - without visualisation - has 12 bytes.
As for "fake" RNGs, there is dozens of them, including the "lodsw" and "scasb" tricks (used in maze 8b.
let me start with the thread i already wrote : HERE
there is a funny and strange relation between fractals and really really good random number generators. i did not (yet) prove or publish what i found, but here is the core routine, displaying what the algorithm generates when it's "forced" to generate a series of ones and zeros.
Code:
push 0xa000
pop es
mov al,0x13
int 0x10
L:
add dx,cx
sar dx,1
salc
jnc B
sub cx,123
B:
sub cx,dx
inc ax
stosb
jmp short L
result:
compare it with the pictures of https://www.random.org/analysis/
good:
bad:
i would still have to run this thingy through all hard statistical tests, and enhance it to 32 or 64bits.
The real core - without visualisation - has 12 bytes.
As for "fake" RNGs, there is dozens of them, including the "lodsw" and "scasb" tricks (used in maze 8b.
obligatory xkcd reference:
Code:
int getRandomNumber()
{
return 4; // chosen by fair dice roll.
// guaranteed to be random.
}
pshufw mm1, mm0, 0x1E
paddd mm0, mm1
paddd mm0, mm1
note: Just Seed mm0 (mm1 is a temp register)
A short one with mediocre outcome, might be good enough for some use cases - it's the simplemost linear congruential generator that has some randomness and loops through all possible values for X, no matter how many bits it consists of:
x = 3*~x
Another one I've used on C64 for initializing $4000..$7FFF (and a few more ones beyond) with very random bytes (the word at $7C points to $3ac9 initially):
loop:
EOR $7D
STA ($7C),Y
JSR $BACD
INY
BNE loop
INC $7D
BPL loop
$BACD just accidentially happens to contain instructions that aid with randomness, I found these with an automated search:
[bacd] ISB $A5B8,Y
[bad0] RRA $6685
[bad3] RTS
x = 3*~x
Another one I've used on C64 for initializing $4000..$7FFF (and a few more ones beyond) with very random bytes (the word at $7C points to $3ac9 initially):
loop:
EOR $7D
STA ($7C),Y
JSR $BACD
INY
BNE loop
INC $7D
BPL loop
$BACD just accidentially happens to contain instructions that aid with randomness, I found these with an automated search:
[bacd] ISB $A5B8,Y
[bad0] RRA $6685
[bad3] RTS
on c64. afaik:
ADC/EOR $a2
if the timer is on.
or a combination of some codes with adc $d012 (raster-ypos).
did that in http://csdb.dk/release/?id=112417.
ADC/EOR $a2
if the timer is on.
or a combination of some codes with adc $d012 (raster-ypos).
did that in http://csdb.dk/release/?id=112417.
7
rnd_func:
move.l #$c001c0de,d0
addq.l #5,d0
rol.l d0,d0
move.l d0,rnd_func+2
rts
move.l #$c001c0de,d0
addq.l #5,d0
rol.l d0,d0
move.l d0,rnd_func+2
rts
