| Author |
Message |
|
Iambian
Advanced Member
Joined: 13 Mar 2004
Posts: 423
|
 Posted: 26 Mar 2010 11:21:58 am Post subject: |
|
|
| I'm looking for a routine (Z80) that generates a random number anywhere between 0 and 255 with a selectable upper bound. The use of ion's random number routine has provided poor results for me (second use isn't random). The TI-OS is not available for use. I would prefer to have my number strictly based on the number that came before it. |
|
| Back to top |
|
|
DrDnar
Member
Joined: 28 Aug 2009
Posts: 116
|
| Posted: 26 Mar 2010 02:59:34 pm Post subject: |
|
|
| WikiTI has one that might work well, depending on what you need. It requires an 8-byte seed, and you'll have to implement the selectable upper bound part yourself. |
|
| Back to top |
|
|
Iambian
Advanced Member
Joined: 13 Mar 2004
Posts: 423
|
| Posted: 26 Mar 2010 10:33:54 pm Post subject: |
|
|
I see the LFSR implementation on wikiti.
Would I still get good results if I implemented a nonzero upper bound this way (assuming I had preserved the contents of B and A held the output number):
Code:
sub b
jr nc,$-1
add a,b
ret
I see ionRand doing it the following way, with the upper bound being in B, the "random" number being in E, and god-knows-what being in L and the same though H=D :
Code:
randomLoop:
add hl,de
djnz randomLoop
ld a,h
Would this be a better way?
Or should I be approaching the upper bound problem in a different way, and if so, what would be a suggestion?
Last edited by Guest on 26 Mar 2010 10:35:01 pm; edited 1 time in total |
|
| Back to top |
|
|
FloppusMaximus
Advanced Member
Joined: 22 Aug 2008
Posts: 472
|
| Posted: 27 Mar 2010 12:03:40 am Post subject: |
|
|
I'm a little confused. Are you saying ionRandom is too random, or not random enough?
Quote: I would prefer to have my number strictly based on the number that came before it.
In other words, you want extremely non-random behavior? (For instance, if you're generating numbers between 1 and 50, you'd want, at best, to see the same sequence of 50 numbers every time?)
As to your second point (essentially, using rand() % n rather than (rand() * n) / 256), that of course depends on how rand() is computed, but what you're suggesting is generally not a good idea. This is because simple random number generators (such as the linear generator used by ionRandom) are much more random in the high bits than in the low bits. (If you think about it, this makes sense: the low bits mix with and contribute additional pseudo-randomness to the high bits, but not vice versa.)
If you're using an LFSR, on the other hand, there's no difference in randomness between the "low" and "high" bits. (On the gripping hand, if you're using an LFSR in combination with something else, the above may still apply.) I think, for a pure LFSR generator, the modulus and division methods are theoretically equivalent, but one or the other might give a better distribution depending on how rounding works (I'm too lazy to do the math at the moment.) Also, think carefully about the period of your LFSR and how many times you clock it for each output value. |
|
| Back to top |
|
|
darkstone knight
Advanced Member
Joined: 07 Sep 2008
Posts: 438
|
| Posted: 27 Mar 2010 05:40:42 am Post subject: |
|
|
Iambian wrote: Would I still get good results if I implemented a nonzero upper bound this way (assuming I had preserved the contents of B and A held the output number):
Code: sub b
jr nc,$-1
add a,b
ret
that wont give you good results, if you, for example, take a bound of 254, the number 1 would be picked twice as often
and if your bound is 250, numbers 0-5 would be picked twice as often.
Quote: I see ionRand doing it the following way, with the upper bound being in B, the "random" number being in E, and god-knows-what being in L and the same though H=D :
Code: randomLoop:
add hl,de
djnz randomLoop
ld a,h
Would this be a better way?
what he is doing is basely the:
rand(0,255)/256*bound
this will give "perfect" resultts (well, the other routine does that too) as long your bound is a power of 2, otherwise it will pick certain numbers more often (in the above example, 127 twice as often)
Quote: Or should I be approaching the upper bound problem in a different way, and if so, what would be a suggestion?
i think you get best results by using ions method using an 16 bit random number:
rand(0,65535)/65536*bound
in this case the error rate between R and R+1 is less than 0.1%
notice that in both cases, it is impossible to roll a value equal to bound, as 65536/65535 < 1
best solution would be, imo, to just re-roll your random routine using bound = 2^x (or 2^x -1, not sure on that one) until you get a number you want, shouldnt take many tries (less than 2 on average) like:
Code:
do {
rand = random(0,power_of_2);
} while (rand > bound)
where power_of_2 is the nearest 2^x above (or equal, ofcourse) your "maximum random number" |
|
| Back to top |
|
|
calcdude84se
Member
Joined: 09 Aug 2009
Posts: 207
|
| Posted: 27 Mar 2010 12:04:50 pm Post subject: |
|
|
FloppusMaximus wrote: In other words, you want extremely non-random behavior? (For instance, if you're generating numbers between 1 and 50, you'd want, at best, to see the same sequence of 50 numbers every time?)
Rather, you would generate numbers between 1 and 1000 in the background, and take it mod 50 (okay, it doesn't work that way since we're starting with 1, not 0, but bear with me) to get a 1000-long sequence of numbers between 1 and 50. |
|
| Back to top |
|
|
Iambian
Advanced Member
Joined: 13 Mar 2004
Posts: 423
|
| Posted: 29 Mar 2010 11:17:44 pm Post subject: |
|
|
Thanks for all the replies. I'll go ahead and see if what I have is good enough for what I need it for.
To FloppusMaximus: My problem with ionRandom is that when I called it for a second time, there just wasn't enough variance in the result to do me any good. It was like some numbers were (greatly) preferred over others.
Last edited by Guest on 30 Mar 2010 12:10:07 am; edited 1 time in total |
|
| Back to top |
|
|
poopslayer78
Newbie
Joined: 10 Sep 2009
Posts: 28
|
| Posted: 04 Apr 2010 01:35:21 pm Post subject: |
|
|
you can just load the refresh register, which increments after each M1 cycle. This is usually random enough for me. Please note, that only bits 0-6 are "random". bit 7 remains as loaded (you can load R to/from A only).
Last edited by Guest on 04 Apr 2010 01:36:54 pm; edited 1 time in total |
|
| Back to top |
|
|
calc84maniac
Elite
Joined: 22 Jan 2007
Posts: 770
|
| Posted: 04 Apr 2010 02:19:35 pm Post subject: |
|
|
poopslayer78 wrote: you can just load the refresh register, which increments after each M1 cycle. This is usually random enough for me. Please note, that only bits 0-6 are "random". bit 7 remains as loaded (you can load R to/from A only).
In the topic description he said he did not want to use this register, because it is only random the first time in a row that you use it. |
|
| Back to top |
|
|
|
Z80 & 68k Assembly => z80 & ez80 Assembly
