Danjovic Posted March 30, 2022 Share Posted March 30, 2022 Does anybody know a good function to generate a random number withing a range delimited by 1 to N being N not a power of two? for instance between 1 and 75 or maybe between 1 and 100 ? Thanks Quote Link to comment Share on other sites More sharing options...
+Andrew Davie Posted March 30, 2022 Share Posted March 30, 2022 53 minutes ago, Danjovic said: Does anybody know a good function to generate a random number withing a range delimited by 1 to N being N not a power of two? for instance between 1 and 75 or maybe between 1 and 100 ? Thanks If you have a multiply, and a random from 0..255... yes. C-like pseudocode.... rndN = ((random & 0xFF) * N) >> 8 Essentially, you treat your generic random (0-255) as a fraction from 0 to 1. When you do the multiply by N, you end up with a 16-bit number whose format is conceptually A.B where A is the whole part and B is the fractional. The shift in the above discards the fractional ,leaving you with a number from 0 to N-1. I use the above in my CDFJ code regularly. But it does require a multiply. 2 Quote Link to comment Share on other sites More sharing options...
Danjovic Posted March 30, 2022 Author Share Posted March 30, 2022 Thanks Andrew! I will try that! I wonder if I discard the numbers above N (picking another in this case), will the probability for numbers below N still equal to each other? Quote Link to comment Share on other sites More sharing options...
Thomas Jentzsch Posted March 30, 2022 Share Posted March 30, 2022 55 minutes ago, Danjovic said: I wonder if I discard the numbers above N (picking another in this case), will the probability for numbers below N still equal to each other? That should be the case, else the generator would have a general bias (even without removing numbers). 1 Quote Link to comment Share on other sites More sharing options...
+Andrew Davie Posted March 30, 2022 Share Posted March 30, 2022 2 hours ago, Danjovic said: Thanks Andrew! I will try that! I wonder if I discard the numbers above N (picking another in this case), will the probability for numbers below N still equal to each other? Yeah, don't do that. Potentially infinite delays while you wait for a number in the desired range to be selected. Depending on N and the repeat-cycle of your random generator. Quote Link to comment Share on other sites More sharing options...
RevEng Posted March 30, 2022 Share Posted March 30, 2022 You just mask first to get a range that's the closest-fitting power-of-two. Worst case you have a range nearly double what you need, and it really doesn't take a lot of iteration to get a pick within the desired range. 1 Quote Link to comment Share on other sites More sharing options...
+Andrew Davie Posted March 30, 2022 Share Posted March 30, 2022 Had a go implementing a simple solution using the algorithm I described. Untested, so be warned! ; pass y = N (range returned is 0..N-1) ; pass rnd = 0..255 random number ; result = the calculated random (from 0 to N-1 inclusive) lda #0 sta result mult clc adc rnd bcc next inc result next dey bne mult 1 1 Quote Link to comment Share on other sites More sharing options...
RevEng Posted March 30, 2022 Share Posted March 30, 2022 2 hours ago, RevEng said: You just mask first to get a range that's the closest-fitting power-of-two. Worst case you have a range nearly double what you need, and it really doesn't take a lot of iteration to get a pick within the desired range. To quantify this, I ran through a few different LFSRs, and it seems the maximum-iterations you'll encounter with this approach (for the worst-case of throwing away half of the range) is equal to the bits in the LFSR. So worst-case is 16 iterations for a 16-bit LFSR, 8 iterations for an 8-bit LFSR. The average case iterations always seems to be nearly 2, regardless of the LFSR size. (all of which makes intuitive sense) The situation improves the closer your range is to a power-of-two. 1 Quote Link to comment Share on other sites More sharing options...
Danjovic Posted March 30, 2022 Author Share Posted March 30, 2022 7 minutes ago, RevEng said: So worst-case is 16 iterations for a 16-bit LFSR, 8 iterations for an 8-bit LFSR. Thanks! I think that even the worst case this is plainly acceptable for what I have in mind. 1 Quote Link to comment Share on other sites More sharing options...
+Andrew Davie Posted March 30, 2022 Share Posted March 30, 2022 (edited) R(17) = R(16) + R(1) R(45) = R(32) + R(8) + R(4) + R(1) R(194) = R(128) + R(64) + R(2) So what I'm thinking with the above is you could hardwire some masking and addition. If you know N as a preset value... using (2^n)-1 as the mask for each component, then you can do an AND For example, R(16) --> "and #15" giving 16 possibilities. So you choose a random range of each of the "1" bits of the N value. so for the first example R(17) = (rnd & 15) + (rnd & 1) You'd need to call rnd several times, or shift so you were using different bits. ; weirdo random 0..16 (inclusive) ; uses R(17) = R(16) + R(1) lda rnd and #15 sta result ; = R(16) lda rnd and #2 lsr ; = R(1), and carry clear adc result ; = R(16) + R(1) ; returned value in A Just throwing this up as an alternate method. I have no idea, other than intuition, that it's valid to sum sub-randoms like this. Its advantages -- fixed time, no multiplies, can be really efficient. Disadvantage - hardwired for a particular N Edited March 30, 2022 by Andrew Davie 1 Quote Link to comment Share on other sites More sharing options...
+Andrew Davie Posted March 30, 2022 Share Posted March 30, 2022 (edited) ; pass N = defines range of random (0..N-1) lda #0 sta result lda #$7F sta mask bitloop asl N bcc nobit lda rnd ; get another random and mask clc adc result sta result nobit lsr mask bne bitloop ; A = random in chosen range Well, the above is untested but I had fun writing it. The idea is that it starts with a mask of 127, and if bit 7 of N is set, then it effectively adds a random (0-127) to the result. And then for bit 6, it adds a random from (0-63)... right down to bit 0 where it adds a random from (0-1). It is supposed to work for any N, and sums randoms masked by (2^N)-1, for each on-bit in the N range. Pretty quick, guaranteed runtime for any given N. I just have a vague suspicion that the concept is faulty -- but I don't yet know why. Somebody should give this a try Edited March 30, 2022 by Andrew Davie 2 Quote Link to comment Share on other sites More sharing options...
RevEng Posted March 30, 2022 Share Posted March 30, 2022 1 hour ago, Andrew Davie said: Just throwing this up as an alternate method. I have no idea, other than intuition, that it's valid to sum sub-randoms like this. Its advantages -- fixed time, no multiplies, can be really efficient. Disadvantage - hardwired for a particular N This gives a non-uniform distribution, with the edges of the range getting lower probability. I actually like this particular method for random screen coordinates, as more middle is more likely than the extremes, which can be seen as a feature. See this post for a graphic of the distribution of a 0-159 range. 1 Quote Link to comment Share on other sites More sharing options...
+Andrew Davie Posted March 30, 2022 Share Posted March 30, 2022 10 minutes ago, RevEng said: This gives a non-uniform distribution, with the edges of the range getting lower probability. I actually like this particular method for random screen coordinates, as more middle is more likely than the extremes, which can be seen as a feature. See this post for a graphic of the distribution of a 0-159 range. Yes, you are right I think. I wrote a short test and binned the frequency for N=9, over 10 million generated randoms, and got.. [645512, 1262827, 1245957, 1245087, 1244236, 1245984, 1243539, 1246423, 620435] It's not a gaussian... just a sharp dropoff on the edges. The middle numbers' frequencies look remarkably consistent. No doubt I've botched the test code 2 Quote Link to comment Share on other sites More sharing options...
+Karl G Posted March 31, 2022 Share Posted March 31, 2022 9 hours ago, RevEng said: To quantify this, I ran through a few different LFSRs, and it seems the maximum-iterations you'll encounter with this approach (for the worst-case of throwing away half of the range) is equal to the bits in the LFSR. So worst-case is 16 iterations for a 16-bit LFSR, 8 iterations for an 8-bit LFSR. I've always avoided the re roll the dice method before, not knowing how many retries might be needed. Knowing the worst case scenario definitely makes this approach much more viable. 1 Quote Link to comment Share on other sites More sharing options...
RevEng Posted March 31, 2022 Share Posted March 31, 2022 Yeah, pretty pleased to quantify that. Plus it was a good excuse to break out lfsr6502 to generate the sequences. 1 1 Quote Link to comment Share on other sites More sharing options...
Danjovic Posted March 31, 2022 Author Share Posted March 31, 2022 Nice way to graphically assess the randomness of an given algorithm! The batari basic's embedded rand16 should fit nicely for me. I understand that the rand16 runs in background, right? Then If I pick a value whenever I press a button It will never repeat a sequence, right? Quote Link to comment Share on other sites More sharing options...
RevEng Posted March 31, 2022 Share Posted March 31, 2022 Thanks! Actually, the bB rand16 gets cranked every time you use it. So something like "myposition = rand & 127" generates assembly code that includes a "jsr randomize" call. It's best practise to seed the generator based on human interaction, like running continuously during a game title screen, so the game will start somewhere unique in the whole sequence. In terms of never repeating, it's worth saying the sequence does repeat after 65535 values, as most 16-bit LFSRs do. 1 Quote Link to comment Share on other sites More sharing options...
Danjovic Posted March 31, 2022 Author Share Posted March 31, 2022 2 hours ago, RevEng said: It's best practise to seed the generator based on human interaction, like running continuously during a game title screen, so the game will start somewhere unique in the whole sequence. That´s great. I should pick a new value every screen then, but I should only use the random value when I press a button. Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.