6502 pseudo random number generator. By Lee Davison
[Back]

This is a short peice of code that generates a maximal length, 8 bit, pseudo random number sequence. This is the 6502 version of Z80 random. A 32 bit 68k version can be found here.

This routine is no great shakes in the speed stakes, it's just a demo of a usefull technique.

; returns pseudo random 8 bit number in A. Affects A, X and Y. ; (r_seed) is the byte from which the number is generated and MUST be ; initialised to a non zero value or this function will always return ; zero. Also r_seed must be in RAM, you can see why...... rand_8 LDA r_seed ; get seed AND #$B8 ; mask non feedback bits ; for maximal length run with 8 bits we need ; taps at b7, b5, b4 and b3 LDX #$05 ; bit count (shift top 5 bits) LDY #$00 ; clear feedback count F_loop ASL A ; shift bit into carry BCC bit_clr ; branch if bit = 0 INY ; increment feedback count (b0 is XOR all the ; shifted bits from A) bit_clr DEX ; decrement count BNE F_loop ; loop if not all done no_clr TYA ; copy feedback count LSR A ; bit 0 into Cb LDA r_seed ; get seed back ROL A ; rotate carry into byte STA r_seed ; save number as next seed RTS ; done r_seed .byte 1 ; prng seed byte (must not be zero)

A maximal length pseudo random number generator is basically just a shif register with feedback from the later stages to generate the next input bit. The form for a generator of length n with feedback from t is shown below.

You don't have to limit the length to only 8 bits, any number of bits from two upwards will work if you chose the right feedback tap(s). Here is a table of some values.

Bits [n]	Tap(s) [t]	Length	Bits [n]	Tap(s) [t]	Length
2	1	3	3	2	7
4	3	15	5	3	31
6	5	63	7	6	127
8	6,5,4	255	9	5	511
10	7	1023	11	9	2047
15	14	32767	16	15,13,4	65535
17	14	131071	18	11	262143
20	17	1048575	21	19	2097151
22	21	4194303	23	18	8388607
24	23,22,17	16777215	25	22	33554431
28	25	268435455	29	27	536870911
31	28	2147483647

In the last case, with 31 bits, if you took a new value once a second the sequence wouldn't repeat for over sixty eight years. Even clocked at 1MHz it would still take almost a minute and a half to cycle through every state.

A sequence generator like this is used to generate values for the RND() function in EhBASIC.

e-mail me