Making a random number in Assembly

Basic and Machine Language

Moderator: Moderators

groepaz
Vic 20 Scientist
Posts: 1180
Joined: Wed Aug 25, 2010 5:30 pm

Re: Making a random number in Assembly

Post by groepaz »

to get a longer sequence you need a generator that creates a longer sequence :) monkey patching it will only make it worse
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 »

groepaz wrote:to get a longer sequence you need a generator that creates a longer sequence :) monkey patching it will only make it worse
Well, it will always start with the same numbers so there is no need for a longer sequence if you can't start at a random point.

I tried to use the rasterline & VIA timers to make the first "seed", e.g. the increment factor. The next call is then used with Mike's proposed 1013904223 increment factor (which can be seen as one of the common used values at https://en.wikipedia.org/wiki/Linear_co ... _generator).

I have no idea if I have broken some rules there, but it seems like my program is not starting with the same series (at least not within my test period), so I guess it gives a useable way to initiate the LCG.

Attached is a program that uses this way to generate random lines on a 192x160 bitmap. The program is 579 bytes, but uses 4K for its bitmap (e.g. 8K+ expansion required). Sources are included. Please note that x & y values are truncated with AND and then added to keep all bits (due to the bitmap not being 256x256), but they are not properly normalized (I was a little too lazy for that).
bam.zip
(2.71 KiB) Downloaded 266 times
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 »

Kakemoms wrote:I tried to use the rasterline & VIA timers to make the first "seed", e.g. the increment factor. The next call is then used with Mike's proposed 1013904223 increment factor (which can be seen as one of the common used values at https://en.wikipedia.org/wiki/Linear_co ... _generator).
You are confusing the seed of the RNG with the increment term of the LCG in charge (especially so in the source). For a LCG, scaling factor and increment term are constants, they keep the same value throughout the whole time the generator is in use, and are *characteristic* of that given implementation, together with the modulo constant. Regardless of what RNG is used, the seed contains the entropy pool that is transformed into a new seed by one call of the RNG. The output number then needs to be derived from the seed after each call of the RNG.
I have no idea if I have broken some rules there, but it seems like my program is not starting with the same series (at least not within my test period), so I guess it gives a useable way to initiate the LCG.
It's generally no good idea to pick apart a number delivered by a RNG and use the parts of it. Especially in case of a LCG, the bits don't share the same properties regarding to randomness. If you take a look at the LSB of the seed, it just changes between 0 and 1 for each call, and so is nowhere as random as, for example, the MSB. This is not a fault of my implementation, this applies to all LCGs. You're misusing the generator, yes.

And it's also not as if I had not already mentioned this peculiar quirk of LCGs, and to quote from there:
Mike wrote:As I wrote earlier, a final multiplication should be used to obtain numbers in the range of 0..R-1 by treating the output as 0:32 fixed-point number. The lower bits of this type of generator aren't as random, so modulo is not recommended.
Emphasis added.
Attached is a program that uses this way to generate random lines on a 192x160 bitmap. The program is 579 bytes, but uses 4K for its bitmap (e.g. 8K+ expansion required). Sources are included. Please note that x & y values are truncated with AND and then added to keep all bits (due to the bitmap not being 256x256), but they are not properly normalized (I was a little too lazy for that).
The address function of the bitmap is significantly simplified, if you arrange the chars column-wise instead of row-wise. Also, that line routine could need a good overhaul, but then we're clearly getting OT here.
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 »

Regarding your last question, as how to obtain a good seed - the standard method uses a timer in conjunction with a non-determined time span. Like for example the time passed between start of the timer, and a key press by the user upon a prompt. You can obtain a 16-bit seed quite easily from timer 1 of VIA #1 (with all its interrupt functions disabled) like thus:

Code: Select all

.02A1  A9 7D     LDA #$7D
.02A3  8D 1E 91  STA $911E
.02A6  A9 82     LDA #$82
.02A8  8D 1E 91  STA $911E
.02AB  A9 40     LDA #$40
.02AD  8D 1B 91  STA $911B
.02B0  A9 FE     LDA #$FE
.02B2  8D 14 91  STA $9114
.02B5  A9 FF     LDA #$FF
.02B7  8D 15 91  STA $9115
.02BA  60        RTS
.02BB  08        PHP
.02BC  78        SEI
.02BD  AE 14 91  LDX $9114
.02C0  AC 15 91  LDY $9115
.02C3  28        PLP
.02C4  E0 04     CPX #$04
.02C6  B0 01     BCS $02C9
.02C8  C8        INY
.02C9  90 01     BCC $02CC ; note: C flag not modified by INY!
.02CB  EA        NOP
.02CC  60        RTS
The timer is started by calling $02A1 and then counts continuously down from 65535 to 0. The routine at $02BB reads out the timer, and corrects the high-byte in Y in case the low-byte underflowed between LDX $9114 and LDY $9115.

You'd then:

- start the timer with JSR $02A1,
- prompt the user to press the fire button,
- first check the fire button is actually released(!),
- then loop until the fire button has been pressed, and finally
- do a JSR $02BB to obtain the 16-bit seed for your RNG.

In case you're wondering why I load the timer latch with $FFFE instead of $FFFF - the timer value always underflows to $FFFF and is only then reloaded from the latch value.


Edit: added the two instructions BCC and NOP at the end to make the timer read out in constant time. So two calls to $02BB can be used to measure cycle counts of small routines.
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: You are confusing the seed of the RNG with the increment term of the LCG in charge (especially so in the source). For a LCG, scaling factor and increment term are constants, they keep the same value throughout the whole time the generator is in use, and are *characteristic* of that given implementation, together with the modulo constant. Regardless of what RNG is used, the seed contains the entropy pool that is transformed into a new seed by one call of the RNG. The output number then needs to be derived from the seed after each call of the RNG.
Ah! What a bummer. I see that now. Thanks for helping with that one!
It's generally no good idea to pick apart a number delivered by a RNG and use the parts of it. Especially in case of a LCG, the bits don't share the same properties regarding to randomness. If you take a look at the LSB of the seed, it just changes between 0 and 1 for each call, and so is nowhere as random as, for example, the MSB. This is not a fault of my implementation, this applies to all LCGs. You're misusing the generator, yes.

The address function of the bitmap is significantly simplified, if you arrange the chars column-wise instead of row-wise. Also, that line routine could need a good overhaul, but then we're clearly getting OT here.
Hmm, yes you did mention that MSB was more random. I was simply too tired to think straight after a week long vacation.. with 3 yelling kids. :lol:

Edit: By experimentation I found that the output value of $06 or $FE (in the code above) is less than random. In fact if I plot with that it gives a very uncentered distribution of the lineplot. But isn't $06 the MSB? and $03 the LSB? Anyway I got better "experimental" results using $04 or $05.

As for random seeds I see your point. When the user types "RUN" and hit enter, the first rasterline & VIA readout is going to be as random as anything else, but to get a true 32-bit random value I will involve some user interaction.

In my future CPLD expansion for the Vic-20 I hope to include a white noise generator. Now, making that in HW is a really interesting question.. but thats in the future.
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 »

Kakemoms wrote:Edit: By experimentation I found that the output value of $06 or $FE (in the code above) is less than random. In fact if I plot with that it gives a very uncentered distribution of the lineplot. But isn't $06 the MSB? and $03 the LSB? Anyway I got better "experimental" results using $04 or $05.
Once again, it's not sensible to pick apart the RNG seed. But anyhow: by construction, the bytes *will* deliver an equidistribution of all values 0..255 when viewed over the whole period of the RNG.

What you can do without resorting to a multiply routine to scale the whole seed by 160 or 192 is - use the MSB of the generator (which is in $06 or $FE) and:

- Call QDRand for the first x co-ordinate from $06, and loop until x1<192,
- Call QDRand for the first y co-ordinate from $06, and loop until y1<160,
- Call QDRand for the second x co-ordinate from $06, and loop until x2<192, and finally
- Call QDRand for the second y co-ordinate from $06, and loop until y2<160.

This uses the 'dice throw and reject'-method. The RNG is assumed to return numbers 0..255 (which are obtained by correctly multiplying the seed with 256 - but here this simply amounts to taking the MSB), and we reject numbers outside the range 0..191 or 0..159 respectively.

In the same way you can make a D5 out of an D6: just throw the die, and re-roll if it shows a 6.
Kakemoms
Vic 20 Nerd
Posts: 740
Joined: Sun Feb 15, 2015 8:45 am

Re: Making a random number in Assembly

Post by Kakemoms »

Aww.. great idea Mike! I'll use that.
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 »

Well, here's the result, using MINIGRAFIK, NR_QDRand and my fast line routine: madness.zip.

(requires +8K RAM expansion, load and run the file "BOOT" to start)

Code: Select all

10 POKE55,0:POKE56,60:CLR:FORT=15360TO16356:READA:POKET,A:NEXT
11 @ON:@CLR:SYS15360
12 :
13 DATA 169,9,133,181,32,54,60,165,142,201,160,176,247,133,251,32,54,60,165,142,201,192
14 DATA 176,247,133,252,32,54,60,165,142,201,160,176,247,133,253,32,54,60,165,142,201
15 DATA 192,176,247,133,254,32,204,60,76,4,60,169,95,133,101,169,243,133,100,169,110
16 DATA 133,99,169,60,133,98,32,135,60,32,181,60,32,195,60,32,161,60,32,195,60,32,135
17 DATA 60,32,161,60,32,195,60,32,135,60,32,181,60,32,195,60,32,181,60,32,195,60,32,161
18 DATA 60,32,195,60,32,161,60,165,101,133,139,165,100,133,140,165,99,133,141,165,98
19 DATA 133,142,96,24,165,101,101,139,133,101,165,100,101,140,133,100,165,99,101,141
20 DATA 133,99,165,98,101,142,133,98,96,24,165,100,101,139,133,100,165,99,101,140,133
21 DATA 99,165,98,101,141,133,98,96,24,165,99,101,139,133,99,165,98,101,140,133,98,96,6
22 DATA 139,38,140,38,141,38,142,96,56,165,253,229,251,176,20,166,251,164,253,132,251
23 DATA 134,253,166,252,164,254,132,252,134,254,73,255,105,1,133,247,160,200,56,165,254
24 DATA 229,252,176,6,160,136,73,255,105,1,133,248,197,247,144,3,76,94,62,204,189,61
25 DATA 240,24,140,189,61,140,209,61,140,229,61,140,249,61,140,13,62,140,33,62,140,53
26 DATA 62,140,73,62,165,181,205,174,61,240,72,141,174,61,141,194,61,141,214,61,141,234
27 DATA 61,141,254,61,141,18,62,141,38,62,141,58,62,201,41,208,5,169,127,56,176,8,169
28 DATA 128,205,175,61,240,32,24,141,175,61,106,141,195,61,106,141,215,61,106,141,235
29 DATA 61,106,141,255,61,106,141,19,62,106,141,39,62,106,141,59,62,165,251,74,74,74
30 DATA 170,189,189,63,133,249,189,209,63,133,250,165,251,41,7,170,189,155,61,141,153
31 DATA 61,189,163,61,141,154,61,165,247,170,74,133,182,232,164,252,56,76,0,0,172,192
32 DATA 212,232,252,16,36,56,61,61,61,61,61,62,62,62,96,177,249,9,128,145,249,202,240
33 DATA 246,165,182,229,248,176,3,101,247,200,133,182,177,249,9,64,145,249,202,240,226
34 DATA 165,182,229,248,176,3,101,247,200,133,182,177,249,9,32,145,249,202,240,206,165
35 DATA 182,229,248,176,3,101,247,200,133,182,177,249,9,16,145,249,202,240,186,165,182
36 DATA 229,248,176,3,101,247,200,133,182,177,249,9,8,145,249,202,240,88,165,182,229
37 DATA 248,176,3,101,247,200,133,182,177,249,9,4,145,249,202,240,68,165,182,229,248
38 DATA 176,3,101,247,200,133,182,177,249,9,2,145,249,202,240,48,165,182,229,248,176,3
39 DATA 101,247,200,133,182,177,249,9,1,145,249,202,240,28,165,182,229,248,176,3,101
40 DATA 247,200,133,182,24,165,249,105,192,133,249,165,250,105,0,133,250,56,76,172,61
41 DATA 96,204,20,63,240,24,140,20,63,140,40,63,140,60,63,140,80,63,140,100,63,140,120
42 DATA 63,140,140,63,140,160,63,165,181,205,13,63,240,72,141,13,63,141,33,63,141,53,63
43 DATA 141,73,63,141,93,63,141,113,63,141,133,63,141,153,63,201,41,208,5,169,127,56
44 DATA 176,8,169,128,205,14,63,240,32,24,141,14,63,106,141,34,63,106,141,54,63,106,141
45 DATA 74,63,106,141,94,63,106,141,114,63,106,141,134,63,106,141,154,63,165,251,74,74
46 DATA 74,170,189,189,63,133,249,189,209,63,133,250,165,251,41,7,170,189,248,62,141
47 DATA 246,62,189,0,63,141,247,62,165,248,170,74,133,182,232,164,252,56,76,0,0,11,31
48 DATA 51,71,91,111,131,151,63,63,63,63,63,63,63,63,96,133,182,177,249,9,128,145,249
49 DATA 202,240,244,200,165,182,229,247,176,238,101,248,133,182,177,249,9,64,145,249
50 DATA 202,240,224,200,165,182,229,247,176,238,101,248,133,182,177,249,9,32,145,249
51 DATA 202,240,204,200,165,182,229,247,176,238,101,248,133,182,177,249,9,16,145,249
52 DATA 202,240,184,200,165,182,229,247,176,238,101,248,133,182,177,249,9,8,145,249,202
53 DATA 240,88,200,165,182,229,247,176,238,101,248,133,182,177,249,9,4,145,249,202,240
54 DATA 68,200,165,182,229,247,176,238,101,248,133,182,177,249,9,2,145,249,202,240,48
55 DATA 200,165,182,229,247,176,238,101,248,133,182,177,249,9,1,145,249,202,240,28,200
56 DATA 165,182,229,247,176,238,101,248,133,182,24,165,249,105,192,133,249,165,250,105
57 DATA 0,133,250,56,76,11,63,96,0,192,128,64,0,192,128,64,0,192,128,64,0,192,128,64,0
58 DATA 192,128,64,17,17,18,19,20,20,21,22,23,23,24,25,26,26,27,28,29,29,30,31
59 :
60 REM ** MG MADNESS WRITTEN 2017-04-20 BY MICHAEL KIRCHER
... :mrgreen:
User avatar
cercamon
Vic 20 Amateur
Posts: 42
Joined: Sun Dec 28, 2014 4:41 am

Re: Making a random number in Assembly

Post by cercamon »

Very useful thread. I'm currently learning to write some code on the Vic-20 and I find the threads in this section so formative and time-saving.

I could use the previous example of the graphic demo released in a D64 file. I've downloaded madness.zip but haven't found a way so far to run in XVIC (Vice) with 8K+ RAM expansion. Any advice? Thanks.
Kakemoms
Vic 20 Nerd
Posts: 740
Joined: Sun Feb 15, 2015 8:45 am

Re: Making a random number in Assembly

Post by Kakemoms »

Rename the "minigrafik" file in Mike's download into "minigrafik.prg". Drag that into xvice. Then copy his basic code from the above post, change case into lower case and paste it into the xvice window (right click mouse in the window will paste it). Type "RUN" and press enter.
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 »

cercamon wrote: I've downloaded madness.zip but haven't found a way so far to run in XVIC (Vice) with 8K+ RAM expansion. Any advice?
Ignore what Kakemoms wrote.

Turn off True Drive Emulation in VICE and enable Virtual device traps. In the "Autostart settings...", make sure PRG autostart mode is set to "Virtual FS".

That being prepared, set VICE to +8K RAM expansion, decompress the directory "madness" from the *.zip file and drag the file "boot" into the xvic main window.

This will mount the surrounding directory, "madness", within VDrive of VICE and autostart the file "boot". The rest will take care for itself. Note the machine code data will take a few seconds to be read in before the lines are drawn.

...

And yes - I *was* too lazy to put this into a *.d64. As is, and decompressed, the whole thing runs fine without issues from a SD2IEC and with VDrive of VICE. If you really want the program in a *.d64 or on a real disk, you'll have to transfer it for yourself.

At last, instead of automagically mounting a directory by dragging a file from that directory into the VICE main window, any directory hosted on the PC can be manually mounted as huge disk in VICE in the "Peripheral settings...". Just make sure to set TDE off and Traps on (as mentioned above), and also tick off "Write P00 files" in case you want to write files to the directory/"disk".
User avatar
cercamon
Vic 20 Amateur
Posts: 42
Joined: Sun Dec 28, 2014 4:41 am

Re: Making a random number in Assembly

Post by cercamon »

Boy, this is really faaast! :-) And I didn't even set the Warp mode.
The lines were drawn at a speed that I actually didn't expect to see in a Vic-20 graphic screen.

Thank you for the instructions, Mike. You make me also find out about the VirtualFS mode of VICE. So far I've always dealt with D64, PRG or CRT files. I'll probably make my own .D64 for "madness" anyway. The MINIGRAFIK library is also very interesting. I'm starting to love this little machine that back in 1982 I totally missed (I bought my C64 in 1985).
aeb
Vic 20 Amateur
Posts: 67
Joined: Sat Jun 19, 2004 2:06 pm

Re: Making a random number in Assembly

Post by aeb »

For example in 0.5K or 1K minigames and such, sometimes all you need is the smallest random number routine. Here's a handy one:

Code: Select all

Random	subroutine
	lda	#$01
	asl
	bcc	.1
	eor	#$4d
.1
	sta	Random+1
	eor	$9124
	rts
It's just a simple 8-bit PRNG, but the output value is shuffled with timer bits.

Why?

8-bit PRNG alone: Boooring, repetitive, predictable, parts of the sequence may be easily memorized
Internal 8-bit PRNG with every output value EOR'ed with cycle timer: Nice! Just what I needed!
Any other solution: Too much / too big / too complex / too bad / too slow :)

To get smaller number ranges AND the output value with $01, $03, $07, $0f, $1f, $3f or $7f.

(If using BCD arithmetics: Use AND-masks $01, $03, $07, $17, $37 or $77. Add two masked random BCD numbers together if you also want the digits 8 and 9 to appear.)

Too random? To get a predetermined sequence of 255 values in range of $01-$ff instead, just remove eor $9124. You can then initialize the random seed at Random+1. Seed $00 hangs the PRNG and also without eor $9124 the routine never outputs a zero.
Kakemoms
Vic 20 Nerd
Posts: 740
Joined: Sun Feb 15, 2015 8:45 am

Re: Making a random number in Assembly

Post by Kakemoms »

aeb wrote:For example in 0.5K or 1K minigames and such, sometimes all you need is the smallest random number routine. Here's a handy one:

Code: Select all

Random	subroutine
	lda	#$01
	asl
	bcc	.1
	eor	#$4d
.1
	sta	Random+1
	eor	$9124
	rts
Too random? To get a predetermined sequence of 255 values in range of $01-$ff instead, just remove eor $9124. You can then initialize the random seed at Random+1. Seed $00 hangs the PRNG and also without eor $9124 the routine never outputs a zero.
Well, at "bcc" the carry is always going to be clear (due to asl which puts "bit7" of $01 into carry), so you could just remove the eor #$4d, meaning this routine is always going to put 1 into Random+1.
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 »

Kakemoms wrote:
aeb wrote:For example in 0.5K or 1K minigames and such, sometimes all you need is the smallest random number routine. Here's a handy one:

Code: Select all

Random  subroutine
        lda     #$01 <------+
        asl                 |
        bcc     .1          |
        eor     #$4d        |
.1                          |
        sta     Random+1 ---+
        eor     $9124
        rts
Too random? To get a predetermined sequence of 255 values in range of $01-$ff instead, just remove eor $9124. You can then initialize the random seed at Random+1. Seed $00 hangs the PRNG and also without eor $9124 the routine never outputs a zero.
Well, at "bcc" the carry is always going to be clear (due to asl which puts "bit7" of $01 into carry), so you could just remove the eor #$4d, meaning this routine is always going to put 1 into Random+1.
Look closer.
Post Reply