;In: nothing
;Out: A with a random number
;Author: Ricardo Bittencourt aka RicBit (BrMSX, Tetrinet and several other projects)
; choose a random number in the set [0,255] with uniform distribution
RAND:
PUSH HL
LD HL,(SEED)
ADD HL,HL
SBC A,A
AND 83h
XOR L
LD L,A
LD (SEED),HL
POP HL
RET

The random number generated will be any number from 0 to FFh.

Despite be a random number generator routine, your results will pass in several statistical tests.

Before the first call, the SEED value must be initiated with a value different of 0.

For a deterministic behavior (the sequence of values will be the same if the program was initiated), use a fixed SEED value.

For a somewhat more random sequence, use:

LD A,(JIFFY);MSX BIOS time variable
OR 80H ;A value different of zero is granted
LD A,(SEED)

The values obtained from this method is much more *random* that what you get from LD A,R.

The JIFFY one only works if you're using the complete standard interrupt handler and have interrupts enabled all the time.

Always the best random generator is using the human interface with a LD A,R or any other (described above) method. Reading the joystick status directly from the PSG ports or some other user-influenceable input is very hard to plan and therefore one of the best methods to implement.

Fully agree with that. And the best solution is using LD A,R and then this A value as an index for a lookup random number table. Please note that only the 7 less significant bits change in R register.

Quote:

The JIFFY one only works if you're using the complete standard interrupt handler and have interrupts enabled all the time.

The JIFFY value could be read in the game start routine once, before the interrupt handler be installed. After all, you only need to set SEED once too.

You could create a time variable in your interrupt handle, and use that variable to initiate the seed value.

Quote:

Always the best random generator is using the human interface with a LD A,R or any other (described above) method. Reading the joystick status directly from the PSG ports or some other user-influenceable input is very hard to plan and therefore one of the best methods to implement.

A good idea to think about. LD A,R will generate numbers almost in sequence if used almost sequentially. This behavior is not useful to use this value without any other treatment. Do you agree?

Quote:

PUSH HL LD HL,(SEED) ADD HL,HL SBC A,A AND 83h XOR L LD L,A LD (SEED),HL POP HL RET

mmm letme see, if i see correctly, it does:
if SEED => 32768 then
SEED = SEED * 2
SEED low byte = SEED low byte XOR 83h
OUT = SEED low byte
else
SEED = SEED * 2
OUT = SEED low byte
end if

mmmmm... it isn't too simply?

in resume: it just multiplies to SEED * 2 and if it overflows the new SEED has its low byte with the bits 0,1 and 7 switched, the rest goes as it is... i am not an expert in this matter.... it is enought?

anyone can test it and to calculate it in a graphic for see the dispersion of the obtained results?

SEED = 1

20000 trials: here you have the histogram (in txt :-) )

0 85
1 74
2 75
3 87
4 62
5 82
6 73
7 84
8 74
9 73
10 83
11 83
12 71
13 78
14 79
15 82
16 81
17 91
18 81
19 81
20 74
21 72
22 77
23 77
24 76
25 77
26 92
27 85
28 80
29 78
30 80
31 83
32 77
33 79
34 91
35 65
36 79
37 86
38 78
39 72
40 76
41 77
42 72
43 78
44 85
45 81
46 83
47 74
48 80
49 75
50 76
51 84
52 85
53 79
54 76
55 72
56 78
57 76
58 80
59 87
60 78
61 80
62 84
63 74
64 83
65 71
66 85
67 79
68 89
69 78
70 71
71 75
72 76
73 85
74 80
75 81
76 86
77 76
78 79
79 78
80 73
81 85
82 73
83 88
84 73
85 77
86 82
87 84
88 82
89 71
90 73
91 74
92 81
93 68
94 75
95 76
96 78
97 76
98 77
99 76
100 71
101 75
102 75
103 72
104 85
105 83
106 77
107 69
108 78
109 75
110 80
111 78
112 75
113 74
114 75
115 81
116 72
117 87
118 78
119 78
120 78
121 70
122 78
123 81
124 83
125 72
126 77
127 77
128 75
129 77
130 71
131 75
132 80
133 89
134 74
135 84
136 83
137 88
138 70
139 68
140 69
141 89
142 83
143 76
144 67
145 80
146 79
147 76
148 82
149 74
150 85
151 79
152 84
153 75
154 73
155 64
156 74
157 78
158 74
159 82
160 83
161 80
162 84
163 71
164 74
165 79
166 82
167 81
168 77
169 74
170 76
171 80
172 77
173 73
174 78
175 77
176 80
177 76
178 77
179 80
180 77
181 73
182 75
183 80
184 77
185 76
186 68
187 76
188 84
189 81
190 76
191 76
192 79
193 74
194 79
195 77
196 77
197 65
198 80
199 86
200 72
201 85
202 79
203 77
204 83
205 74
206 78
207 74
208 75
209 78
210 73
211 80
212 82
213 76
214 69
215 75
216 82
217 81
218 76
219 80
220 83
221 76
222 83
223 80
224 80
225 74
226 75
227 82
228 82
229 89
230 86
231 82
232 78
233 75
234 89
235 77
236 78
237 72
238 79
239 73
240 81
241 77
242 79
243 80
244 75
245 85
246 78
247 76
248 84
249 83
250 75
251 84
252 82
253 73
254 82
255 77

and the matlab code:

SEED = 1;

T=[];

for n=1:20000


if SEED >= 32768

SEED = bitand(SEED * 2, 2^16-1);

SEED = bitxor(SEED,131);

OUT = bitand(SEED , 255);

else

SEED = SEED * 2;

OUT = bitand(SEED , 255);

end

T = [T; OUT];

end

The data seems more o less uniform

that is really not ramdon! that has a pattern

SBC A,A will turn all A bits equal Carry Flag. This will be used to calculate SEED LSB.

;Carry Flag=0 => A=0, Carry Flag=1 => A=FFh
SBC A,A
;A and 83h
AND 83h
;A xor SEED LSB
XOR L

Carry Flag come from the overflow of ADD HL,HL.

Am I correct?

Yes, you are correct, by that reason i see that is too simply, because here alone is a transportation of the bit 15 of SEED (in each LOOP) to the bit 7, 1 and 0, plus that no data enters in the bit 0, so, bit 0 alone is the overflowed bit 15. So really, you got bit 7 and 1 switched according the the bit 15.

a very real ramdon number is too hard to obtain. Indeed there is books that only are dedicated to this matter.
You can make complex or less complex calculations but with the time and certain ammount of loops it will always back to a previously given pattern.

The secret is how to do a pattern that returns all the values of the range, each value in an equal proportion..

So, to test a ramdon generator you needs to do it

like in 10.000 executions.... how much times it returns 0, how much times it returns 1.... how much times it returns 2....... how much times it returns 255....

then make a graphic, with X axis the VALUE returned.... and Y axis the ammount of time that the value was returned....
if that graphic has a LINE, and not mountains or peaks-up or peaks-down.... you got it!. The perfect one!

I cannot see any pattern!!

Each bin in the histogram I have posted is very close to 78.1250 wich is the expected value (20000/256).
In my opinion this is a nice random number generator, at least excellent for game programming.

Actually this is a variation of a method known as linear congruence generator.
The pattern really is periodic, but the period can be very large and the goodness
of the seguence dependes on the initial paramenters

the average needs to be 78
there is values with 64 times.... and others returned 89 times
that trace a line of 27! from min to max

mmmm...

well, as i said i am not an expert in this matter

The range is narrow, in your sample at least, because you used 1 for initiate SEED, no?

Do you have tested with other values?

no
but actually the seed should not be very relevant, becouse, if the
generator i sgood, SEED, while the loop is working, should pass
trough all the 2^16-1 values except zero.
In this case you have the maxlengh random pediod (wich is of course
2^16-1 )

The true parameters are 2 and 131 that decide IF SEED passes
trough all the admissible values, ie if you are generating a
maxlengh random sequence.

Hi people

This routine is a very optimized Linear Feedback Shift Register (LFSR). Please read any book on random number generation to learn how it works. It's exactly the same method used in hardware, inside the PSG, to generate the random noise channel. It's also used inside CDMA cell phones, and anything else using spread spectrum techniques. Linear congruence generators, such as the one used inside MSX BASIC, are much slower than LFSR.

This particular implementation has indeed a maxlength sequence (65535), actually it's the smallest 16-bit LFSR known (this can be proven by brute force search in the number of taps). If you iterate the algorithm 65535 times, you will see that the distribution is quite uniform.

The generated sequence *has* a pattern, of course, it's a 65535-size pattern that repeats over and over. This can't be avoided with pseudo-random numbers. The only way to avoid this is increasing the range of the number, say, making all the calculations with 24 bits. This would be much slower, and not really useful for practical purposes as game programming.

The seed can be any value different from 0 (I use JIFFY OR 1, but actually any value is fine).

Of course, you don't need to believe me in that, just load the 65535-pattern in matlab and perform some statistical tests. Knuth's "Art of Computer Programming" has a lot of tests you could apply to the data.

Some considerations about LFSR can be found on the wikipedia: http://en.wikipedia.org/wiki/LFSR