News:

Printed Amstrad Addict magazine announced, check it out here!

Main Menu
avatar_EgoTrip

Random Number Generator in Machine Code

Started by EgoTrip, 09:39, 16 December 10

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

EgoTrip

How do I generate random numbers in machine code? For example a number between 1 and 20?


Thanks.

redbox

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.  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 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.

arnoldemu

#2
Quote from: redbox on 09:56, 16 December 10
There are some examples on the wiki.  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 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.
My games. My Games
My website with coding examples: Unofficial Amstrad WWW Resource

Phi2x

#3
.

AMSDOS

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
* Using the old Amstrad Languages :D   * with the Firmware :P
* I also like to problem solve code in BASIC :)   * And type-in Type-Ins! :D

Home Computing Weekly Programs
Popular Computing Weekly Programs
Your Computer Programs
Updated Other Program Links on Profile Page (Update April 16/15 phew!)
Programs for Turbo Pascal 3

Phi2x

#5
.

redbox

#6
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

EgoTrip

Thanks for the help people, I will let you know how it goes.

redbox

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?

&BD0DKL TIME PLEASE
ActionReturns the time that has elapsed since the computer was switched on or reset (in 1/300ths of a second)
EntryNo entry conditions
ExitDEHL contains the four byte count of the time elapsed, and all other registers are preserved
NotesD 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.

Devilmarkus

In BASIC you should use RANDOMIZE TIME ;)
When you put your ear on a hot stove, you can smell how stupid you are ...

Amstrad CPC games in your webbrowser

JavaCPC Desktop Full Release

AMSDOS

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!  :)
* Using the old Amstrad Languages :D   * with the Firmware :P
* I also like to problem solve code in BASIC :)   * And type-in Type-Ins! :D

Home Computing Weekly Programs
Popular Computing Weekly Programs
Your Computer Programs
Updated Other Program Links on Profile Page (Update April 16/15 phew!)
Programs for Turbo Pascal 3

arnoldemu

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?

&BD0DKL TIME PLEASE
ActionReturns the time that has elapsed since the computer was switched on or reset (in 1/300ths of a second)
EntryNo entry conditions
ExitDEHL contains the four byte count of the time elapsed, and all other registers are preserved
NotesD 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.

My games. My Games
My website with coding examples: Unofficial Amstrad WWW Resource

Phi2x

#12
.

AMSDOS

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.
* Using the old Amstrad Languages :D   * with the Firmware :P
* I also like to problem solve code in BASIC :)   * And type-in Type-Ins! :D

Home Computing Weekly Programs
Popular Computing Weekly Programs
Your Computer Programs
Updated Other Program Links on Profile Page (Update April 16/15 phew!)
Programs for Turbo Pascal 3

Nich

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 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. ;))

Nich

I have just added the information in my previous post to the CPCWiki article. I hope no one minds me putting the BASIC section before the machine code section! :laugh:

AMSDOS

Looks like the Cat is amongst the Pigeons now Nich!  ;)
* Using the old Amstrad Languages :D   * with the Firmware :P
* I also like to problem solve code in BASIC :)   * And type-in Type-Ins! :D

Home Computing Weekly Programs
Popular Computing Weekly Programs
Your Computer Programs
Updated Other Program Links on Profile Page (Update April 16/15 phew!)
Programs for Turbo Pascal 3

AMSDOS

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.
* Using the old Amstrad Languages :D   * with the Firmware :P
* I also like to problem solve code in BASIC :)   * And type-in Type-Ins! :D

Home Computing Weekly Programs
Popular Computing Weekly Programs
Your Computer Programs
Updated Other Program Links on Profile Page (Update April 16/15 phew!)
Programs for Turbo Pascal 3

AMSDOS

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

* Using the old Amstrad Languages :D   * with the Firmware :P
* I also like to problem solve code in BASIC :)   * And type-in Type-Ins! :D

Home Computing Weekly Programs
Popular Computing Weekly Programs
Your Computer Programs
Updated Other Program Links on Profile Page (Update April 16/15 phew!)
Programs for Turbo Pascal 3

ralferoo

#19
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.

ralferoo

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 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 x^3 + x^2 + 1 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: x^{ 8 }+x^{ 6 }+x^{ 5 }+x^{ 4 }+1. 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


ralferoo

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! :)

ralferoo

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



MaV

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.

Black Mesa Transit Announcement System:
"Work safe, work smart. Your future depends on it."

Alcoholics Anonymous

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

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

Patrik implemented a z80 version for 8-bit random numbers here:
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

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

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.

Powered by SMFPacks Menu Editor Mod