Making a random number in Assembly

Basic and Machine Language

Moderator: Moderators

Kakemoms
Vic 20 Nerd
Posts: 740
Joined: Sun Feb 15, 2015 8:45 am

Making a random number in Assembly

Post by Kakemoms »

Hi

I have been plundering around and trying to get random numbers. After thinking about it and not finding anything useful on the net I came up with this method:
- Get 3 random seed numbers, 1 from rasterline position, 2 from VIA counters (they are fetched at program start)
- Make 3 virtual "oscillators" and are 3 words that increase by each random seed from a simple add.
- Execute the "oscillators" for some time interval

To get the random number each 16-bit oscillator produces a 8-bit byte by adding MSB+LSB.

Calculate the random number as:

((MSB1+LSB1)*(MSB2+LSB2))+(MSB3*256+LSB3)

The result is a 16-bit random number. You can reduce it to 8-bit by adding MSB+LSB.

The code:

Code: Select all

tab44=$1D00      ; use a page of mem (multiplication)

start
        lda     $9119
        sta     randomseed
        lda     $9004
        sta     randomseed+1
        cmp     $9004
        beq     *-3
        lda     $9118
        sta     randomseed+2
        jsr     initmult

	ldx	#$ff
rndlp1	ldy	#$ff
rndlp2
	jsr	randomize
	dey
	bne	rndlp2
	dex
	bne	rndlp1
	
	jsr	get16rand

	rts

randomize
        ; "oscillates" 3 different 16-bit numbers based on 3 seeds
        lda     randomosc
        clc
        adc     randomseed
        sta     randomosc
        lda     randomosc+1
        adc     #0
        sta     randomosc+1
        lda     randomosc+2
        clc
        adc     randomseed+1
        sta     randomosc+2
        lda     randomosc+3
        adc     #0
        sta     randomosc+3
        lda     randomosc+4
        clc
        adc     randomseed+2
        sta     randomosc+4
        lda     randomosc+5
        adc     #0
        sta     randomosc+5
        rts

get16rand
        lda     randomosc
        clc
        adc     randomosc+1
        tax
        lda     randomosc+2
        adc     randomosc+3
        tay
        jsr     mult88f         ;Result in $92-$93
        lda     randomosc+4
        clc
        adc     $92
        tax
        lda     randomosc+5
        adc     $93
        tay
        rts     ;random number in x & y register
        
; lower4bits=l4b
; higher4bits=h4b
; utilize x=l4bx+16*h4bx and y=l4by+16*h4by
; x*y=14bx*14by+l4bx*16*h4by+16*h4bx*l4by+16*16*h4bx*h4by
; Multiplication routine for faster multiplication


initmult         ; set up 15x15 multiplication table
        ldx     #$f
im1     ldy     #$f
im2     jsr     mult44
        sta     $96
        iny
        txa
        asl
        asl
        asl
        asl
        sta     im3+1
        lda     $96
im3     sta     tab44,y
        dey
        bne     im2
        dex
        bne     im1
        rts

mult44  ; Mike's 4x4 multiplication code
        DEY            ; 2 To counteract carry add: %1111->%1110 + C
        STY $96        ; 3
        TXA            ; 2
        ASL            ; 2
        ASL            ; 2
        ASL            ; 2
        ASL            ; 2 %XXXX0000
        ASL            ; 2 %XXX00000
        BCC rm0        ; 3
        ADC $96        ; 3 %XXX01111
rm0     ASL            ; 2 %XX011110
        BCC rm1        ; 3
        ADC $96        ; 3 %XX011110+1110+c=%11101101
rm1     ASL            ; 2 %X1011010
        BCC rm2        ; 3
        ADC $96        ; 3 %X1011010+1110+c=%X1101001
rm2     ASL            ; 2 %11010010
        BCC rm3        ; 3
        ADC $96        ; 3 %11010010+1110+c=%11100001=225=15*15
rm3     RTS            ; 2


mult88f

        txa             ;2
        and     #$f     ;2

        sta     m4s1+1  ;4

        asl             ;2
        asl             ;2
        asl             ;2
        asl             ;2
        sta     m4u1+1  ;4
; 20c
        txa             ;2 
        and     #$f0    ;2 
        sta     m4s2+1  ;4

        lsr             ;2
        lsr             ;2
        lsr             ;2
        lsr             ;2 (c=0)

        sta     m4s3+1  ;4 
; 20c
        tya             ;2
        and     #$f0    ;2 h4by
        tax             ;2
        tya             ;2
        and     #$f     ;2 l4by
        tay             ;2

m4s1    lda     tab44,x ;5 l4bx*h4by
m4s2    adc     tab44,y ;5 h4bx*l4by - c=0, overflow in carry
; 22c
        sta     $92     ;3
;        and     #$f0    ;4 highest bits unnecessary -> lowest bits cleared
        ror             ;2 shift right and put carry in bit7
        lsr             ;2
        lsr             ;2
        lsr             ;2 all bits in bit4-bit0
        sta     $93     ;3 high byte result (e.g. *16)

        lda     $92     ;3
        and     #$f     ;2
        asl             ;2
        asl             ;2
        asl             ;2
        asl             ;2 *16
 ;       sta     $92     ;3 low byte result

m4u1    adc     tab44,y ;5 l4bx*l4by
 ;       adc     $92     ;3 add low byte, overflow->carry (kept until adc)
        sta     $92     ;3
        lda     $93     ;3
m4s3    adc     tab44,x ;5 h4bx*h4by*16*16, add overflow carry
        ;adc     $93     ;3 result high byte, add overflow carry
        sta     $93     ;3
; 108cycles for 8-bit*8-bit multiplication
        rts


randomseed
        byte    0,0,0
randomosc
        word    0,0,0
I am hoping that the 3 "oscillators" will give a very long series of random numbers without repeat. Having 3 seeds also help in not producing the same series, but there is a slight chance that this may happen. Increasing the number of "oscillators" (&seeds) will reduce the chance, but it will not get to zero.

I am not using the VIA's, but they would practically do the same thing. As the code is in assembly, the timing will always be the same (the code runs at the same speed), so only some artificial "oscillator" will work.

For the C64 someone used the noise generator to get random numbers, but I can't see how this could be done on the Vic-20.

For simplicity I put the "randomizer" in a nested loop to run it >65000 times before it gets the random number. In a program (game or whatever) you would simply use "randomizer" as part of the interrupt/game loop.

Any suggestions would be appreciated.
User avatar
darkatx
Vic 20 Afficionado
Posts: 470
Joined: Wed Feb 04, 2009 2:17 pm
Location: Canada

Re: Making a random number in Assembly

Post by darkatx »

Learning all the time... :)
groepaz
Vic 20 Scientist
Posts: 1180
Joined: Wed Aug 25, 2010 5:30 pm

Re: Making a random number in Assembly

Post by groepaz »

using hardware counters like these for "random numbers" really isnt a good idea - mostly because the numbers are far from random. also depending on at what time they are generated, the behaviour of the generated sequence can change in radical and surprising ways - which is usually not what you want either. you can produce much better sequences using some simple LFSR code, something like this: http://codebase64.org/doku.php?id=base: ... rs_as_lfsr
I'm just a Software Guy who has no Idea how the Hardware works. Don't listen to me.
User avatar
Mike
Herr VC
Posts: 4816
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Re: Making a random number in Assembly

Post by Mike »

Timers are useful for generating a seed for a pseudo-random-number-generator (PRNG), provided their read-out is coupled with some non-deterministic delay, like human input (as in: "press fire to start game").

From then, the method should be purely deterministic. As the seed of the PRNG gives a finite number of states, at some time the PRNG will loop. Any good (read: not broken) generator produces all possible numbers of its seed range with the exception of only a few ones, in one long cycle, and wildly permuted. From there, numbers in a certain range are best produced by treating the output as binary fraction between 0 and 1, multiplying with the range R and rounding down to get integers in the range 0..R-1.

At some time, I reproduced the PRNG of the ZX81 for use in a WIP. It is a Lehmer random number generator with (effectively) a 16-bit seed, and it works as follows:

Code: Select all

X    := (75 * X ) MOD 65537; X  = 1..65536
 n+1           n              n
Its period is 65536. X_n must never be zero. Actually, what is stored in memory is X_n - 1 as 16-bit value, so X_n=0 can't happen anyway. When this value is multiplied with a small 8-bit constant R to form a 24-bit product, the top byte directly gives random numbers in the range 0..R-1.

There are far better generators available, but I know this one works... within its little scope.

Here's a simple implementation in BASIC (download):

Code: Select all

1 INPUT"SEED";S
2 S=INT(S)
3 IFS<0ORS>65535THEN1
4 :
5 X=S+1
6 X=75*X:X=X-65537*INT(X/65537)
7 S=X-1
8 PRINTS/65536
9 GOTO5
groepaz
Vic 20 Scientist
Posts: 1180
Joined: Wed Aug 25, 2010 5:30 pm

Re: Making a random number in Assembly

Post by groepaz »

Timers are useful for generating a seed for a pseudo-random-number-generator (PRNG), provided their read-out is coupled with some non-deterministic delay, like human input (as in: "press fire to start game").
yes. on the CBM 8bits also the rastercounter can be very useful for this (just read it when the program starts, for example)
I'm just a Software Guy who has no Idea how the Hardware works. Don't listen to me.
User avatar
GreyGhost
Vic 20 Nerd
Posts: 525
Joined: Wed Oct 05, 2005 11:10 pm

Re: Making a random number in Assembly

Post by GreyGhost »

I've often thought about having a person type something in such as their name or what not, then using what they typed along with a time resulting from how long it took them to type it in to generate the seed. Obviously this wouldn't be practical in every instance, but at the start of a game or something, it could be used to start the randomization.
Rob
Kakemoms
Vic 20 Nerd
Posts: 740
Joined: Sun Feb 15, 2015 8:45 am

Re: Making a random number in Assembly

Post by Kakemoms »

groepaz wrote:
Timers are useful for generating a seed for a pseudo-random-number-generator (PRNG), provided their read-out is coupled with some non-deterministic delay, like human input (as in: "press fire to start game").
yes. on the CBM 8bits also the rastercounter can be very useful for this (just read it when the program starts, for example)
Which is basically what the code does, plus it uses VIA1 counters to get two more. One could also use the VIA2 to get another two. With 5 seeds the chance that you end up with the same (pseudo) random number sequence two times is quite small but not zero.

Using auto compile+launch on VICE tend to give the same timing and thus sometimes one do get the same random numbers. On an "normal" Vic-20 the user would have to type LOAD and stuff which takes time, so the VIC counters and rasterline position is going to be random. Now, if one foresees that the program/game one is making ends up on a future MEGACART or something, that may not be true. So ANY user input is needed to get a true random seed.

I was looking into ways to use the Noise generator on the Vic-20, but there is just no input from it, so unless there is some hidden VIA bits finding their way to some memory location (or pseudo memory location), I don't see a way of using it. Anyway, it would be fun to find something so maybe I need to write a program that scans a real Vic-20 memory for erratically changing bits.. (now there goes the rest of the year...). :lol:
groepaz
Vic 20 Scientist
Posts: 1180
Joined: Wed Aug 25, 2010 5:30 pm

Re: Making a random number in Assembly

Post by groepaz »

Using auto compile+launch on VICE tend to give the same timing and thus sometimes one do get the same random numbers.
use a recent nightly build and that doesnt happen (it randomly delays a bit before "run")
I'm just a Software Guy who has no Idea how the Hardware works. Don't listen to me.
User avatar
darkatx
Vic 20 Afficionado
Posts: 470
Joined: Wed Feb 04, 2009 2:17 pm
Location: Canada

Re: Making a random number in Assembly

Post by darkatx »

What about the high nybble from the colour memory is that random?
Learning all the time... :)
User avatar
Mike
Herr VC
Posts: 4816
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Re: Making a random number in Assembly

Post by Mike »

No. It depends on what VIC fetched in the preceding (half-)cycle as high nibble of text screen or character data. The CPU then reads those bits as remnants which remain for a short time on the data bus due to its parasitic capacitance.
User avatar
vicist
Vic 20 Afficionado
Posts: 352
Joined: Tue Oct 09, 2012 5:26 am
Location: Sheffield, UK

Re: Making a random number in Assembly

Post by vicist »

What happened to the rnd function in the latest nightly build of vice???
Using this format of rnd to pick a number between 1 and 100 only produces either a 1 or 100, nothing in between.

Code: Select all

print int(rnd(0)*100)+1
Works ok in stable version 2.4.

Definitely needs looking into.
User avatar
Mike
Herr VC
Posts: 4816
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Re: Making a random number in Assembly

Post by Mike »

On the contrary one needs to wonder if it actually even ever worked on real hardware (I'd need to check this):

RND(0) derives its seed from a VIA timer, the same timer is used to trigger the interrupt which polls the keyboard. There are good chances, that the timer has always (nearly) the same value (a few cycles of interrupt jitter nonwithstanding) between the recognition of the RETURN key and calculating RND(). And this gives nonwhere near random results.
groepaz
Vic 20 Scientist
Posts: 1180
Joined: Wed Aug 25, 2010 5:30 pm

Re: Making a random number in Assembly

Post by groepaz »

rnd(0) shows exactly the irritating behaviour that is expected when using hw counters for "random numbers" :)

and i very much doubt there is a problem with the emulator related to that - if anything VIA and VIC emulation improved (a lot even) since 2.4
I'm just a Software Guy who has no Idea how the Hardware works. Don't listen to me.
Kakemoms
Vic 20 Nerd
Posts: 740
Joined: Sun Feb 15, 2015 8:45 am

Re: Making a random number in Assembly

Post by Kakemoms »

Mike wrote:Timers are useful for generating a seed for a pseudo-random-number-generator (PRNG), provided their read-out is coupled with some non-deterministic delay, like human input (as in: "press fire to start game").

From then, the method should be purely deterministic. As the seed of the PRNG gives a finite number of states, at some time the PRNG will loop. Any good (read: not broken) generator produces all possible numbers of its seed range with the exception of only a few ones, in one long cycle, and wildly permuted. From there, numbers in a certain range are best produced by treating the output as binary fraction between 0 and 1, multiplying with the range R and rounding down to get integers in the range 0..R-1.

At some time, I reproduced the PRNG of the ZX81 for use in a WIP. It is a Lehmer random number generator with (effectively) a 16-bit seed, and works as follows:

Code: Select all

X    := (75 * X ) MOD 65537; X  = 1..65536
 n+1           n              n
Its period is 65536. X_n must never be zero. Actually, what is stored in memory is X_n - 1 as 16-bit value, so X_n=0 can't happen anyway. When this value is multiplied with a small 8-bit constant R to form a 24-bit product, the top byte directly gives random numbers in the range 0..R-1.

There are far better generators available, but I know this one works... within its little scope.
Its a good one, the Lehmer method, but for me a period of 65536 is a little short. Using larger numbers quickly escalates the problem so that it takes a long time to produce the random number on a Vic-20. But yes, mathematically its a much better way. I will have to think about it.

My method with three 16-bit oscillators will ensure no repetition within a very long series of numbers. But I agree that the starting point may break it down as it depends on three 8-bit numbers (and they may have some unforeseen dependence). And not really random since there is a pattern in three interfering oscillators. Maybe I can use the Lehmer to modify the oscillator frequencies to make it more random..
User avatar
vicist
Vic 20 Afficionado
Posts: 352
Joined: Tue Oct 09, 2012 5:26 am
Location: Sheffield, UK

Re: Making a random number in Assembly

Post by vicist »

Obviously, no-one has tried the code snippet I posted above into the latest build of xvic.

I wasn't referring to how random the numbers were that were produced by the code, but that it only produced a 1 or 100 when run.

It works ok in x64 or x128 or xplus4 - just not in xvic.

@ groepaz
The rnd(0) function in xvic is BROKEN :(
rnd(1) seems to work ok :roll:
Last edited by vicist on Sat Mar 05, 2016 4:39 pm, edited 1 time in total.
Post Reply