Random Functions britlion Posting Freak Posts: 805 Threads: 135 Joined: Apr 2009 Reputation: 5 06-18-2012, 11:07 PM 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 FUNCTION``` This 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 SUB```The above function depends on my timer function, which gets the value in FRAMES: Code:```FUNCTION FASTCALL t() as uLong asm     DI     LD DE,(23674)     LD D,0     LD HL,(23672)     EI end asm end function``` This 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 FUNCTION```it's worth noting that the issue with this is that it basically rolls a random, and if it's bigger than limit, it rolls another one. This could potentially take a while, and isn't guaranteed to be fast. Though the probability of failing to hit the zone is kept to 50%, so on average it will roll 1.5 random numbers, I think, per call. This should usually be faster than a floating point multiply, I believe. If 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 FUNCTION``` Timings: 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()-time``` 20,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. britlion Posting Freak Posts: 805 Threads: 135 Joined: Apr 2009 Reputation: 5 06-19-2012, 12:27 AM 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. slenkar Senior Member Posts: 282 Threads: 48 Joined: Feb 2011 Reputation: 0 06-19-2012, 04:19 AM so to get the fastest random number generator you have to use randombase, t() , the seed function, and randombin together britlion Posting Freak Posts: 805 Threads: 135 Joined: Apr 2009 Reputation: 5 06-19-2012, 11:56 AM 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. britlion Posting Freak Posts: 805 Threads: 135 Joined: Apr 2009 Reputation: 5 06-19-2012, 12:35 PM 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. boriel Administrator Posts: 1,757 Threads: 55 Joined: Aug 2019 Reputation: 24 06-20-2012, 07:01 AM 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 * 128`Not only generates an RND float number (0, 1), but also multiplies it by another float, 128. Thus much slower than the others. 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). :?: britlion Posting Freak Posts: 805 Threads: 135 Joined: Apr 2009 Reputation: 5 06-20-2012, 04:09 PM 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. Code:`PRINT RND * 128`Not only generates an RND float number (0, 1), but also multiplies it by another float, 128. Thus much slower than the others. 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. « Next Oldest | Next Newest »