Making a random number in Assembly
Moderator: Moderators
Re: Making a random number in Assembly
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.
Re: Making a random number in Assembly
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.groepaz wrote:to get a longer sequence you need a generator that creates a longer sequence monkey patching it will only make it worse
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).
- Mike
- Herr VC
- Posts: 4870
- Joined: Wed Dec 01, 2004 1:57 pm
- Location: Munich, Germany
- Occupation: electrical engineer
Re: Making a random number in Assembly
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.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).
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.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.
And it's also not as if I had not already mentioned this peculiar quirk of LCGs, and to quote from there:
Emphasis added.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.
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.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).
- Mike
- Herr VC
- Posts: 4870
- Joined: Wed Dec 01, 2004 1:57 pm
- Location: Munich, Germany
- Occupation: electrical engineer
Re: Making a random number in Assembly
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:
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.
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
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.
Re: Making a random number in Assembly
Ah! What a bummer. I see that now. Thanks for helping with that one!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.
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.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.
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.
- Mike
- Herr VC
- Posts: 4870
- Joined: Wed Dec 01, 2004 1:57 pm
- Location: Munich, Germany
- Occupation: electrical engineer
Re: Making a random number in Assembly
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.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.
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.
Re: Making a random number in Assembly
Aww.. great idea Mike! I'll use that.
- Mike
- Herr VC
- Posts: 4870
- Joined: Wed Dec 01, 2004 1:57 pm
- Location: Munich, Germany
- Occupation: electrical engineer
Re: Making a random number in Assembly
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)
...
(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
Re: Making a random number in Assembly
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.
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.
Re: Making a random number in Assembly
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.
- Mike
- Herr VC
- Posts: 4870
- Joined: Wed Dec 01, 2004 1:57 pm
- Location: Munich, Germany
- Occupation: electrical engineer
Re: Making a random number in Assembly
Ignore what Kakemoms wrote.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?
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".
Re: Making a random number in Assembly
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).
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).
Re: Making a random number in Assembly
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:
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.
Code: Select all
Random subroutine
lda #$01
asl
bcc .1
eor #$4d
.1
sta Random+1
eor $9124
rts
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.
Re: Making a random number in Assembly
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.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:
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.Code: Select all
Random subroutine lda #$01 asl bcc .1 eor #$4d .1 sta Random+1 eor $9124 rts
- Mike
- Herr VC
- Posts: 4870
- Joined: Wed Dec 01, 2004 1:57 pm
- Location: Munich, Germany
- Occupation: electrical engineer
Re: Making a random number in Assembly
Look closer.Kakemoms wrote: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.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:
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.Code: Select all
Random subroutine lda #$01 <------+ asl | bcc .1 | eor #$4d | .1 | sta Random+1 ---+ eor $9124 rts