Making a random number in Assembly

Basic and Machine Language

Moderator: Moderators

groepaz
Vic 20 Nerd
Posts: 548
Joined: Wed Aug 25, 2010 5:30 pm

Re: Making a random number in Assembly

Postby groepaz » Sat Apr 08, 2017 10:04 am

to get a longer sequence you need a generator that creates a longer sequence :) monkey patching it will only make it worse

User avatar
Kakemoms
Vic 20 Afficionado
Posts: 465
Joined: Sun Feb 15, 2015 8:45 am

Re: Making a random number in Assembly

Postby Kakemoms » Sat Apr 08, 2017 11:00 am

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_congruential_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 4 times

User avatar
Mike
Herr VC
Posts: 2925
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Re: Making a random number in Assembly

Postby Mike » Sun Apr 09, 2017 6:08 am

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_congruential_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: 2925
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Re: Making a random number in Assembly

Postby Mike » Sun Apr 09, 2017 6:21 am

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.

User avatar
Kakemoms
Vic 20 Afficionado
Posts: 465
Joined: Sun Feb 15, 2015 8:45 am

Re: Making a random number in Assembly

Postby Kakemoms » Sun Apr 09, 2017 10:50 am

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: 2925
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Re: Making a random number in Assembly

Postby Mike » Sun Apr 09, 2017 12:01 pm

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.

User avatar
Kakemoms
Vic 20 Afficionado
Posts: 465
Joined: Sun Feb 15, 2015 8:45 am

Re: Making a random number in Assembly

Postby Kakemoms » Sun Apr 09, 2017 1:51 pm

Aww.. great idea Mike! I'll use that.

User avatar
Mike
Herr VC
Posts: 2925
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Re: Making a random number in Assembly

Postby Mike » Thu Apr 20, 2017 3:34 am

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

madness.zip
(2.51 KiB) Downloaded 14 times

(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:


Return to “Programming”

Who is online

Users browsing this forum: No registered users and 1 guest