+- Forum (https://www.boriel.com/forum)
+-- Forum: Compilers and Computer Languages (https://www.boriel.com/forum/forumdisplay.php?fid=12)
+--- Forum: ZX Basic Compiler (https://www.boriel.com/forum/forumdisplay.php?fid=11)
+---- Forum: How-To & Tutorials (https://www.boriel.com/forum/forumdisplay.php?fid=13)
+---- Thread: Random Functions (/showthread.php?tid=470)
Random Functions - britlion - 06-18-2012
Boriel has included a better random function in the code; but this passes through floating point numbers, which is potentially fairly slow - and for games we usually require integer numbers anyway!
I've written a few functions that are a possible alternative.
This is the base function that does the hard work of generating a random number from 0-255 in the A register (or as a return value, conveniently enough). This is the same random number generator that Boriel is using, incidentally. (Based pretty much wholly on Patrik Rak's stream random generator).
Code:
FUNCTION FASTCALL randomBase () as uByte
ASM
random: ld hl,$A280 ; xz -> yw
ld de,$C0DE ; yw -> zt
ld (random+1),de ; x = y, z = w
ld a,e ; w = w ^ ( w << 3 )
add a,a
add a,a
add a,a
xor e
ld e,a
ld a,h ; t = x ^ (x << 1)
add a,a
xor h
ld d,a
rra ; t = t ^ (t >> 1) ^ w
xor d
xor e
ld h,l ; y = z
ld l,a ; w = t
ld (random+4),hl
;ret (Not necessary, since the compiler will add ret to the end)
END ASM
END FUNCTIONThis function will update the seed value based on the current frames counter. To improve randomness, get the user to have a human interaction that can take a variable amount of time and then run this.
Code:
SUB FASTCALL updateSeed()
REM Updates the random generator seed from the FRAMES system variable.
t()
ASM
LD A,E
EX DE,HL
LD HL,random+2
XOR (HL)
AND A
JR NZ,updateSeedNotZero
INC A
updateSeedNotZero:
LD (HL),A
LD HL,random+4
LD A,E
XOR (HL)
LD (HL),A
INC HL
LD A,D
XOR (HL)
LD (HL),A
END ASM
END SUBCode:
FUNCTION FASTCALL t() as uLong
asm
DI
LD DE,(23674)
LD D,0
LD HL,(23672)
EI
end asm
end functionThis function returns a value from zero to the specified limit number (limit <= 255)
Code:
FUNCTION fastcall randomBin(limit as uByte) as uByte
ASM
AND A
RET Z ; Input zero, output zero.
LD B,A ; Save A
LD C,255
randomBinLoop:
RLA
JR C, randomBinLoopExit
RR C
JR randomBinLoop ; loop back until we find a bit.
randomBinLoopExit:
randomBinRedoCall:
call random
AND C
CP B
RET Z
JR NC, randomBinRedoCall
END ASM
END FUNCTIONIf you do want a number a random number between 0 and 1, using FIXED is quite a lot faster than float. This routine uses randombase to do that:
Code:
FUNCTION FASTCALL randomFixed() as FIXED
ASM
call random
push AF
call random
ld l,A
POP AF
ld h,a
ld d,0
ld e,d
END ASM
END FUNCTIONTimings:
Code:
dim time as uLong
DIM n as uInteger
DIM variable as uByte
time=t()
for n=0 to 20000
REM One line of the following three:
'variable=rnd*128
'variable=randomFixed()*128
'variable=randomBin(128)
next n
print t()-time20,000 loops took:
variable=rnd*128 => 1180 frames.
variable=randomFixed()*128 => 613 Frames (1.92 x faster)
variable=randomBin(128) => 74 frames. (this example is 16 x faster) (worst case averages 13x faster; best case averages 22x faster)
(This does vary by limit, but is never > 89 frames for any limit chosen. Can be as low as about 52. Average is about 64.)
All three, of course, return an integer from 0 to 127 (the last 0-128; this chosen because it's a worse case scenario for timing).
For scale, 20,000 loops calling randomBase takes 37 frames. Of course, this returns a number from 0-255 regardless, with no option to set the upper bound.
Re: Random Functions - britlion - 06-19-2012
For those that are curious, bored, or obsessive about numbers (me) here are the relative timings for each possible output:
You can clearly see the timings increase as we cross a bit boundary (that is, limit requires more bits). This is because probability of rolling higher than the limit increases here - and decreases fairly linearly until the next bit boundary, when it jumps up.
For values at bitboundary upper limits, if you can, choose the faster route
Limit Frames for 20,000
0 23 (really, you want a number from 0-0? You're going to get 0! There's definitely a faster way of calculating zero...)
1 82 Faster route: baseRandom bAND 1
2 86
3 78
4 89
5 82
6 77
7 74 Faster route: baseRandom bAND 7
8 88
9 84
10 81
11 77
12 75
13 73
14 71
15 69 Faster route: baseRandom bAND 15
16 87
17 84
18 82
19 80
20 78
21 76
22 75
23 73
24 72
25 70
26 69
27 68
28 67
29 66
30 66
31 65 Faster route: baseRandom bAND 31
32 84
33 82
34 80
35 79
36 78
37 77
38 76
39 75
40 74
41 73
42 72
43 71
44 70
45 70
46 69
47 69
48 68
49 67
50 67
51 66
52 66
53 65
54 65
55 64
56 64
57 63
58 63
59 62
60 62
61 61
62 61
63 61 Faster Route: baseRandom bAND 63
64 80
65 79
66 78
67 77
68 77
69 76
70 76
71 75
72 74
73 74
74 73
75 73
76 72
77 71
78 71
79 71
80 70
81 70
82 69
83 69
84 68
85 68
86 68
87 67
88 67
89 66
90 66
91 66
92 65
93 65
94 65
95 64
96 64
97 64
98 63
99 63
100 63
101 62
102 62
103 62
104 61
105 61
106 61
107 61
108 60
109 60
110 60
111 60
112 59
113 59
114 59
115 59
116 59
117 58
118 58
119 58
120 58
121 57
122 57
123 57
124 57
125 57
126 57
127 56 Faster route: baseRandom bAND 127
128 75
129 75
130 75
131 74
132 74
133 73
134 73
135 73
136 72
137 72
138 72
139 72
140 71
141 71
142 70
143 70
144 70
145 69
146 69
147 69
148 69
149 69
150 68
151 68
152 68
153 68
154 67
155 67
156 67
157 67
158 66
159 66
160 66
161 66
162 65
163 65
164 65
165 65
166 65
167 64
168 64
169 64
170 63
171 63
172 63
173 63
174 63
175 63
176 62
177 62
178 62
179 62
180 62
181 61
182 61
183 61
184 61
185 61
186 60
187 60
188 60
189 60
190 60
191 60
192 60
193 59
194 59
195 59
196 59
197 59
198 59
199 58
200 58
201 58
202 58
203 58
204 58
205 58
206 57
207 57
208 57
209 57
210 57
211 57
212 56
213 56
214 56
215 56
216 56
217 56
218 56
219 56
220 56
221 55
222 55
223 55
224 55
225 55
226 55
227 55
228 55
229 54
230 54
231 54
232 54
233 54
234 54
235 54
236 54
237 54
238 54
239 53
240 53
241 53
242 53
243 53
244 53
245 53
246 53
247 53
248 53
249 53
250 52
251 52
252 52
253 52
254 52
255 52 Much faster to use randomBase to get 0-255.
I know. Waaay overboard. Mostly did this just to reassure myself there weren't any exceptionally slow points, or corner cases. There was a bug, which I think I've fixed
In short: I put this forward as a faster random number generator than using floating point numbers.
Re: Random Functions - slenkar - 06-19-2012
so to get the fastest random number generator you have to use
randombase,
t() ,
the seed function,
and randombin
together
Re: Random Functions - britlion - 06-19-2012
The time function t() and updateSeed() work together - you only need those if you want to re-seed.
randomBase gives you a number from 0-255 (very quickly)
randomBin (with an awful name. Should probably be randomLimit) gives you 0-n
You can probably see it's trivial to do other ranges.
10-20 would be randomBin(10)+10 for example.
Re: Random Functions - britlion - 06-19-2012
Of course this is only going to make a big difference if you are doing a lot of random numbers! Not worth using the space for this if it's just one or two. However some games do require a LOT of random data to be generated, and you'd see the difference using this suite.
E.g. generating a whole random landscape.
Re: Random Functions - boriel - 06-20-2012
RND was made float to be 100% compatible with Sinclair BASIC. In fact, much of it slowness comes from multiplying with another float number. E.g.
Code:
PRINT RND * 128I think it could be possible to put your routine in the library while taking the code fron rnd.asm (which already contains the random bit generator you use here). :?:
Re: Random Functions - britlion - 06-20-2012
boriel Wrote:RND was made float to be 100% compatible with Sinclair BASIC. In fact, much of it slowness comes from multiplying with another float number. E.g.
Not only generates an RND float number (0, 1), but also multiplies it by another float, 128. Thus much slower than the others.Code:PRINT RND * 128
Oh, absolutely. You did it completely right for the compiler - as I noted in the original post "going through float" is the slow part. My ugly hack here actually, rather than multiplies up numbers, even rolls a new random number until it finds one smaller than the specified limit. This, on average, is actually faster than a multiply, however. Unless there's a long string of fails.
boriel Wrote:I think it could be possible to put your routine in the library while taking the code fron rnd.asm (which already contains the random bit generator you use here). :?:
Yes - I think it might. The trick is to be able to call it and be sure it's in the final code - doesn't the compiler cut it out if rnd isn't used?
I suppose an initialise routine might do the trick.