tiny pseudo random generator

category: code [glöplog]
give your tips and tricks for tiny prng here.

Code:inc al xor al, ah ror al, 1 xchg ah, al

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:
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.
added on the 2015-11-23 16:48:15 by rudi rudi
;;;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
added on the 2015-11-23 18:52:37 by g0blinish g0blinish
This is an honest Galois-type LSFR for Z80:
Code:add ix, ix sbc a and #BD ; instead of #BD, one can use #3F or #D7 xor ixl ld ixl, a

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.
added on the 2015-11-23 19:00:09 by introspec introspec
introspec: very good. did you use that in BB? btw, BB is very kewl.
added on the 2015-11-23 19:02:27 by rudi rudi
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:
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, a

BB uses feedback constant #1B and a slightly different form of code, which is clumsier than this.
added on the 2015-11-23 20:33:46 by introspec introspec
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.
added on the 2015-11-23 20:56:30 by rudi rudi
rudi, yes, not a problem, just write to zxintrospec@gmail.com and I'll be happy to help.
added on the 2015-11-23 21:04:32 by introspec introspec
introspec: thank you
added on the 2015-11-23 21:20:05 by rudi rudi
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
added on the 2015-11-23 22:06:17 by 4mat 4mat
Code: lodsw

(drops mic)
added on the 2015-11-26 09:07:20 by trixter trixter
@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.

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

BB Image

compare it with the pictures of https://www.random.org/analysis/

BB Image

BB Image

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.
added on the 2015-11-26 18:19:52 by HellMood HellMood
obligatory xkcd reference:
Code:int getRandomNumber() { return 4; // chosen by fair dice roll. // guaranteed to be random. }
added on the 2015-11-26 19:25:10 by merkur merkur
pshufw mm1, mm0, 0x1E
paddd mm0, mm1
added on the 2015-11-26 19:55:13 by T21 T21
note: Just Seed mm0 (mm1 is a temp register)
added on the 2015-11-26 20:00:03 by T21 T21
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):

STA ($7C),Y
BNE loop
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
added on the 2015-11-26 21:43:21 by Kabuto Kabuto
on c64. afaik:
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.
added on the 2015-11-26 23:05:43 by rudi rudi
added on the 2015-11-27 07:36:35 by v3nom v3nom
move.l #$c001c0de,d0
addq.l #5,d0
rol.l d0,d0
move.l d0,rnd_func+2
added on the 2015-11-28 19:15:09 by lsl lsl