How do I generate random numbers in machine code? For example a number between 1 and 20?
Thanks.
Quote from: EgoTrip on 09:39, 16 December 10
How do I generate random numbers in machine code? For example a number between 1 and 20?
There are some examples on the wiki (http://www.cpcwiki.eu/index.php/Programming:Random_Number_Generator). Generally you either use a simple formula based function (which is usually enough) or a look-up table.
When I wanted some random numbers generated for the snow in my last demo (http://www.cpcwiki.eu/index.php/Xmas_2010_Demo) I resorted to just using BASIC (using RND to generate the number and then POKEing it into memory) to generate a table. In the demo. this table was then offset on the screen when repeating which was enough to provide a 'random' effect.
Quote from: redbox on 09:56, 16 December 10
There are some examples on the wiki (http://www.cpcwiki.eu/index.php/Programming:Random_Number_Generator). Generally you either use a simple formula based function (which is usually enough) or a look-up table.
When I wanted some random numbers generated for the snow in my last demo (http://www.cpcwiki.eu/index.php/Xmas_2010_Demo) I resorted to just using BASIC (using RND to generate the number and then POKEing it into memory) to generate a table. In the demo. this table was then offset on the screen when repeating which was enough to provide a 'random' effect.
I will add that most of these give you a number in the range 0-255.
After you got that value you can do a "modulus" to get the number into your range
(e.g. divide this number by your upper end of your range and take the remainder).
This is a modulus:
result = result - ((result\range)*range)
to give the remainder "\" is an "integer division".
So for a range 1-20 I advise:
(1 = lower_value)
(20 = upper_value)
final = lower_value + (result-((result\(upper_value-lower_value))*(upper_value-lower_value);
an example in asm is:
call rand8
ld l,a
ld h,0
ld bc,upper_value-lower_value
mod_loop:
or a
sbc hl,bc
jp p,mod_loop
add hl,bc
ld bc,lower_value
add hl,bc
ld a,l
ret
This performs a kind of division by repeat subtraction of the range. When it goes negative it stops, because the value is less than your range, adds the range back on to make it go back positive to get the remainder.
Then it returns it in the A register.
.
phi2x wrote:
If you only need -one- random number in your code, or if you need a seed for your random number generator, you can simply use the register R of the z80 (ie. LD A,R).
It will give you a number between 0 and &7f.
Could that work as a 16bit value if I used it with HL, DE or BC?
Like this:
LD L,R
LD H,R
.
Quote from: phi2x on 11:36, 16 December 10
And the bad news is that only the first value you get from R is "truely" random. If you get R values multiple times, the next value of R is the same as the one before, only incremented by some offset.
If you wanted to generate a 16-bit random number (only once of course), you could use R for the higher byte and then use it as the seed for a routine to generate the low byte.
ld a,r
ld h,a
.rand8
ld b,a
add a,a
add a,a
add a,b
inc a
ld (rand8+1),a
ld l,a ; HL now contains a random 16-bit number
Thanks for the help people, I will let you know how it goes.
If you need a seed to make the number more random, you could also find the time since the CPC was turned on and use that?
| &BD0D | KL TIME PLEASE |
| Action | Returns the time that has elapsed since the computer was switched on or reset (in 1/300ths of a second) |
| Entry | No entry conditions |
| Exit | DEHL contains the four byte count of the time elapsed, and all other registers are preserved |
| Notes | D holds the most signifilcant byte of the time elapsed, and L holds the least significant; the four byte count overflows after approximately l66 days have elapsed. |
In BASIC you should use RANDOMIZE TIME ;)
redbox wrote:
If you wanted to generate a 16-bit random number (only once of course), you could use R for the higher byte and then use it as the seed for a routine to generate the low byte.
ld a,r
ld h,a
.rand8
ld b,a
add a,a
add a,a
add a,b
inc a
ld (rand8+1),a
ld l,a ; HL now contains a random 16-bit number
Looks like a nifty routine! :)
Quote from: redbox on 13:56, 16 December 10
If you need a seed to make the number more random, you could also find the time since the CPC was turned on and use that?
| &BD0D | KL TIME PLEASE |
| Action | Returns the time that has elapsed since the computer was switched on or reset (in 1/300ths of a second) |
| Entry | No entry conditions |
| Exit | DEHL contains the four byte count of the time elapsed, and all other registers are preserved |
| Notes | D holds the most signifilcant byte of the time elapsed, and L holds the least significant; the four byte count overflows after approximately l66 days have elapsed. |
In Blue Angel 69 I created my own time seed. The number incremented every vsync.
I then used this to seed the random number generator, and then from there I retrieved multiple random numbers for my routine.
The important thing here is to understand:
1. the frequency at which you update this seed
2. the frequency at which you take your seed value for the generator
I had a bug, where I was incrementing the seed every interrupt. But I was taking the seed every vsync. So effectively the seed was taken at every multiple of 6. It didn't make it as random as it should. So I just incremented at the same rate as I took the seed, and it worked much better.
.
I've noticed in BASIC that anyone can use a value when assigning a value to the RANDOMIZE procedure and even more annoying is the RANDOMIZE TIME which produces a really random feel to anything which uses it! :(
Turbo Pascal can RANDOMIZE, but it won't randomize to an amount specified because it won't allow it, therefore something like this would have to be done differently to obtain a similar effect. A value which maybe used in BASIC for example after the RANDOMIZE - "RANDOMIZE 10" may look like this I guess:
var seed : byte;
begin
randomize;
seed:=random(10);
write(seed);
end.
however simulating "RANDOMIZE TIME" would be harder to do, perhaps using KL TIME PLEASE would return the kind of value one would use to simulate TIME.
Quote from: Devilmarkus on 13:59, 16 December 10
In BASIC you should use RANDOMIZE TIME ;)
Even
RANDOMIZE TIME sometimes isn't good enough. Try this code to see what I mean:
10 MODE 2
20 FOR a=1 TO 23
30 RANDOMIZE TIME
40 FOR b=1 TO 25
50 PRINT USING("## ");INT(RND*100);
60 NEXT b
70 PRINT
80 NEXT aAfter you obtain about five or six numbers, the numbers are no longer random! However, if you re-initialise the random number seed by using
RANDOMIZE TIME:RANDOMIZE RND, the quality of the random numbers is
much better. (This was something I learnt from a listing in
Computing with the Amstrad. ;))
I have just added the information in my previous post (http://cpcwiki.eu/forum/index.php/topic,1719.msg17234.html#msg17234) to the CPCWiki article (http://www.cpcwiki.eu/index.php/Programming:Random_Number_Generator). I hope no one minds me putting the BASIC section before the machine code section! :laugh:
Looks like the Cat is amongst the Pigeons now Nich! ;)
I had a similar problem generating random numbers between 0 & 2 and came up with this routine in Assembly...
;; Return a number between 0 and 2
org &4000
ld a,(seed)
ld b,a
add a,a
add a,a
add a,b
inc a
ld (seed),a
cp 0
jr c,skip_divide ;; Skip if Number equals 0
.return rra
cp 3
jr nc,return ;; Repeat if number 3 or greater
.skip_divide ld (result),a
ret
.seed defb 0
.result defb 0
...which works for my purpose, though it's not by any means perfect. For example I was varying the values after the "cp" instruction, earlier I had "2" so if a value was 2 or more it would skip the Divide and put the value of A into Result, otherwise if the value was 4 or more it would Rotate A right, though in the odd case it was giving me a result of 0 for when I was trying to generate random numbers of 1,2 & 3. My theory was the 8bit number generator would always produce a result of 1 or more, so I'm unsure what's going wrong with it.
I came up with this which now fixes any numbers smaller than the first comparison check, if a result is 1 though it will jump to the end without dividing the result. If a number is divided so many times and returns a value of 3 it makes it 0, there seems to be a lot of zero's coming up with this though, so I'm open to any suggestions on how to get values between 0 & 2, otherwise it seems okay.
;; Return a number between 0 and 2
org &4000
ld a,(seed)
ld b,a
add a,a
add a,a
add a,b
inc a
ld (seed),a
cp 1
jr z,enter_result ;; Skip if Number equals 1
.return rra
cp 3
jr z,make_zero ;; If result is 3 make it 0
cp 4
jr nc,return ;; Repeat if number is 4 or more
jr enter_result ;; Need to skip Make_Zero at this point
.make_zero xor a
.enter_result ld (result),a
ret
.seed defb 0
.result defb 0
The simplest approach is to maintain the randomness as 8-bit or 16-bit or whatever, then do e.g.:
LD H,0
LD L,A
LD D,0
LD E,A
ADD HL,HL
ADD HL,DE ; HL=3*rand
LD A,H ; HL is now between 0 and 2
I've written it out in long-form so you can see the general approach which can be applied to any range.
You start with something that's in the range 0..255. In maths, we could think of this as [0,256) - the square bracket means the lower bound is included in the set, the round bracket means the upper bound isn't. If you think of it in this sense, you can divide by 256 to get a fractional number in the range [0.0,1.0). Of course, division by 256 is easy - it's just losing a byte of the number.
So, if we multiply this by 3 and divide by 256, we then get a number in the range [0.0,3.0) - the numbers will be approximately evenly distributed but as 256 isn't divisible by 3 exactly (85 remainder 1), 0 will appear 86 times, 1 and 2 only 85 times.
This approach also expects the random number to be truly random within the 8-bit range. Your simple r'=(r*5+1) mod 256 won't have this property, it'll instead loop something like 0,0,0,1,1,2,2,0,0... If this is an issue, you add a few RRCAs before the code above which will move the lower bits to the high bits and so they will have more effect on the randomness produced. You'd be better off using an LFSR generator, but this is where it starts getting complicated.
So, I thought I'd do a separate post about LFSR as it's complicated to explain. For some background reading, see Linear feedback shift register - Wikipedia, the free encyclopedia (http://en.wikipedia.org/wiki/Linear_feedback_shift_register) especially the section on Galois LFSRs as that's what we'll be using. Now, this will seem very complicated, but actually you don't really need to understand it and it's actually very simple to use... :)
So, the idea for generating the polynomial is dividing by a polynomial (which is something like (http://upload.wikimedia.org/math/7/1/4/71497ea092c4d81ff11c1810f0e7bc32.png) modulo some number). This looks and sounds very scary, but actually if we limit the scope of what we're doing, it becomes very easy (like a lot of things in maths). If we choose the modulus to be 2, we can work easy in binary space and treat a single bit as a term in the polynomial. So, for instance, we can express the polynomial above as 1101. Now, addition modulo 2 is just the XOR operator (1 XOR 0=1, 1 XOR 1=0 just like 1+0=1,1+1=2 but 2 mod 2=0). So we can express addition of this polynomial mod 2 as (n XOR %1101).
I'll gloss over the reasons for what we're doing exactly, but essentially the complicated sounding "dividing the current polynomial c by another polynomial p modulo q" when q=2 turns out to be easily expressible in terms of two cases:
if c>p: c'=(c>>1) XOR p
if c<=p: c'=(c>>1)
Moreover, if we choose an arbitrary n, we can find a polynomial with a maximum coefficient of x^n that has a period of (2^n)-1.
This is great for our use, it means if we take n=8 (the size of a byte), we can find a polynomial that gives us a pattern that repeats with period 255. If you look at the table in wikipedia, one such polynomial is: (http://upload.wikimedia.org/math/2/9/0/29076bd037c6fe71f5f9856e7516cd1d.png). If we express this in our binary notation, this becomes 101110001, or in hex #171.
If we were implementing this in C, we could write something like:
if (c&1)
c = (c^0x171) >>1; // note that the high bit is always 1
else
c = c>>1; // note that the high bit is always 0
But we can actually make this even better on the Z80. Consider the comments above and the RRCA instruction. RRCA achieves >>1, and it sets carry if we need to do the XOR case, and moreover, it leaves the high bit set correctly. This means, we can then code this as:
rrca
jr nc,noxor
xor #38
noxor:
Now, you might wonder where the #38 comes from. This value is actually (#171>>1) XOR #80. As the RRCA has already left the high bit set, we don't need to set it with the XOR, and we also don't need to set the low bit (because we're shifting it away). So that polynomial above of 101110001 we can think of as x0111000x. Discarding the x's, we get %0111000, or #38.
There are other interesting properties of polynomials, e.g. the reverse bit pattern also has the same bit pattern, so 100011101 -> #e is also a suitable value for the XOR.
You can verify the period of this random number generator easily by making a test case and then examining memory:
org #800
ld hl,#8100 ; the buffer from #8100 contains the count of each rnd
ld de,#8000 ; the buffer from #8000 contains the sequence of rnd
ld b,0
ld a,1
clear:
ld (hl),e
inc l
djnz clear
loop:
ld (de),a
inc de
ld l,a
inc (hl)
rrca
jr nc,noxor
xor #e
noxor:
djnz loop
ret
So, taking both those last posts together, your random number between 0 and 2 generator could be written like this:
rand:
ld a,#01 ; note we want to avoid 0 as a starting condition as that will always result in an output of 0
rrca
jr nc,rand_noxor
xor #e
rand_noxor:
ld (rand+1),a
ld h,0
ld d,0
ld l,a
ld e,a
add hl,hl
add hl,de
ld a,h
ret
Note that the multiply by 3 could be optimised further, but I'll leave that as an exercise to you! :)
Incidentally as an aside, this is can be turned into a CRC routine very simply (this was the original application):
crc: xor #ff ; initial CRC value
ld b,8
crcloop:
rrca
jr nc,crc_noxor
xor #e
crc_noxor:
djnz crcloop
ld (crc+1),a
ret ; returns current CRC value
Quote from: ralferoo on 14:31, 20 March 14
ld h,0
ld d,0
ld l,a
ld e,a
add hl,hl
add hl,de
ld a,h
Note that the multiply by 3 could be optimised further, but I'll leave that as an exercise to you! :)
Hm, how about this for the above (untested):
ld h,0
ld l,a
add hl,hl
add l
ld h,a
adc 0
If I counted that correctly, it's 3µs less, one byte shorter, and doesn't use the DE register.
Quote from: ralferoo on 14:25, 20 March 14
So, I thought I'd do a separate post about LFSR as it's complicated to explain. For some background reading, see Linear feedback shift register - Wikipedia, the free (http://en.wikipedia.org/wiki/Linear_feedback_shift_register)
An LFSR is better than that other code snippet, but it's still not a very high quality method for random number generation -- there are better available that can also be efficiently implemented on the z80.
This topic was also discussed on WOS some time ago, when Patrik Rak came across a paper by Marsaglia that describes a simple XOR method that does well on tests for randomness: http://www.jstatsoft.org/v08/i14/paper (http://www.jstatsoft.org/v08/i14/paper)
Patrik implemented a z80 version for 8-bit random numbers here:
http://www.worldofspectrum.org/forums/showpost.php?p=583693&postcount=3 (http://www.worldofspectrum.org/forums/showpost.php?p=583693&postcount=3)
There's a bit of self-modifying code to store the seed but you can do away with that.
I wrote a 15-bit random number generator using results from the same paper, which you can see here:
http://z88dk.cvs.sourceforge.net/viewvc/z88dk/z88dk/libsrc/_DEVELOPMENT/stdlib/z80/asm_rand.asm?revision=1.6&view=markup (http://z88dk.cvs.sourceforge.net/viewvc/z88dk/z88dk/libsrc/_DEVELOPMENT/stdlib/z80/asm_rand.asm?revision=1.6&view=markup)
The C standard requires 15-bits (rather an signed int with result always positive), hence the less compact version. Using two 8-bits generated successively by the 8-bit routine would introduce correlations within the 16-bit number generated.
Patrik also tried an 8-bit cmwc implementation here:
http://www.worldofspectrum.org/forums/showthread.php?t=39632&highlight=cmwc (http://www.worldofspectrum.org/forums/showthread.php?t=39632&highlight=cmwc)
He never answered my question there but it looked to me that you couldn't just set any seed value you wanted. If someone is interested in that they should probably take a closer look.
try rnd()mod 20
Quote from: Nich on 12:16, 23 December 10
Even RANDOMIZE TIME sometimes isn't good enough. Try this code to see what I mean:
10 MODE 2
20 FOR a=1 TO 23
30 RANDOMIZE TIME
40 FOR b=1 TO 25
50 PRINT USING("## ");INT(RND*100);
60 NEXT b
70 PRINT
80 NEXT a
After you obtain about five or six numbers, the numbers are no longer random! However, if you re-initialise the random number seed by using RANDOMIZE TIME:RANDOMIZE RND, the quality of the random numbers is much better. (This was something I learnt from a listing in Computing with the Amstrad. ;))
Embarrasing late to the party, but I'm actually surprised nobody commented on this previously. You aren't supposed to call RANDOMIZE repeatedly, because every time you do it resets the seed so you'll end up using the same small subset of the PRNG.
The "correct" way to do the above in BASIC would be more like:
10 MODE 2
20 RANDOMIZE TIME
30 FOR a=1 TO 23
40 FOR b=1 TO 25
50 PRINT USING("## ");INT(RND*100);
60 NEXT b
70 PRINT
80 NEXT awhich moves the seed generation outside of the loop and thus generates a much more random sequence.
Perhaps someone more wiki-knowledgable could correct the entry?
Quote from: andycadley on 21:40, 20 November 14
Embarrasing late to the party, but I'm actually surprised nobody commented on this previously. You aren't supposed to call RANDOMIZE repeatedly, because every time you do it resets the seed so you'll end up using the same small subset of the PRNG.
The "correct" way to do the above in BASIC would be more like:
10 MODE 2
20 RANDOMIZE TIME
30 FOR a=1 TO 23
40 FOR b=1 TO 25
50 PRINT USING("## ");INT(RND*100);
60 NEXT b
70 PRINT
80 NEXT a
which moves the seed generation outside of the loop and thus generates a much more random sequence.
Perhaps someone more wiki-knowledgable could correct the entry?
I think you haven't fully understood what I was trying to convey with my example program.
Most programs that use RANDOMIZE TIME will only use it once, as is the case in the BASIC program you've posted. However, try running that program, resetting it, then running it again, resetting it again, running it a third time, resetting it again... After about six or seven numbers, the same sequence of numbers is generated (93, 54, 6, 98, 14, 3, 18, 35...)! Hence there is a need to use RANDOMIZE TIME:RANDOMIZE RND to reinitialise the seed and prevent the same sequence of 'random' numbers being generated every time you run a program.
The attached screenshots demonstrate the problem more clearly.
[attach=2] [attach=3] [attach=4] [attach=5]