## Making a random number in Assembly

Basic and Machine Language

Moderator: Moderators

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

### Re: Making a random number in Assembly

Kakemoms wrote:Its a good one, the Lehmer method, but for me a period of 65536 is a little short. [...] My method with three 16-bit oscillators will ensure no repetition within a very long series of numbers.

The three 16-bit oscillators will also repeat at the latest after 65536 calls. Possibly earlier, with a period of a lower power of 2. Then the period of all 3 oscillators can only be the lowest common multiply, not bigger than 65536. So you're not better off at the moment.

A linear congruential generator (multiply-add) with a 32-bit seed and modulus also a power of 2 shouldn't be too hard to build on the 6502, NR suggest:

Code: Select all

`X    := (1664525 * X  + 1013904223) MOD 2^32 n+1                n`

You only need to produce the lowest 32 bit of the product. 1664525 is %110010110011000001101 in binary, so this requires ten 32 bit-additions and the corresponding shifts of the seed for the multiply and a single 32-bit addition of 1013904223 in the end. *)

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 example above also has a period of 2^32, which may or may not cover your needs.

*) actually, only 6 shifts are necessary here, as shifts modulo 8 can be produces by using the factor shifted by whole bytes... also, the additions needn't be done in order.
Last edited by Mike on Sat Mar 05, 2016 5:31 pm, edited 2 times in total.

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

### Re: Making a random number in Assembly

vicist wrote: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 function in xvic is BROKEN

If this is supposed to be a bug report, please put this into the bug monitor of VICE at sourceforge, and state the exact release number and platform.

Then there are chances, that one of the maintainers actually takes a look at it, and verifies whether the VIA emulation has been screwed up.

vicist
Vic 20 Devotee
Posts: 229
Joined: Tue Oct 09, 2012 5:26 am
Location: Surrey, UK

### Re: Making a random number in Assembly

OK. Will do.

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

### Re: Making a random number in Assembly

[NR QDRand ...] Here we go:

Code: Select all

`; QDRand of NR in 65xx assembly:;; X    := (1664525 * X  + 1013904223) MOD 2^32;  n+1                n;; 1664525 = %00011001 01100110 00001101;.NR_QDRand LDA #\$5F:STA \$03 ; init result with 1013904223 = \$3C6EF35F LDA #\$F3:STA \$04 LDA #\$6E:STA \$05 LDA #\$3C:STA \$06                  JSR NR_QDRand_00:JSR NR_QDRand_02 ; add factors 2^0 and 2^16 JSR NR_QDRand_03:JSR NR_QDRand_01                  ; add factor 2^9 JSR NR_QDRand_03:JSR NR_QDRand_00:JSR NR_QDRane_01 ; add factors 2^2 and 2^10 JSR NR_QDRand_03:JSR NR_QDRand_00:JSR NR_QDRand_02 ; add factors 2^3 and 2^19 JSR NR_QDRand_03:JSR NR_QDRand_02                  ; add factor 2^20 JSR NR_QDRand_03:JSR NR_QDRand_01                  ; add factor 2^13 JSR NR_QDRand_03:JSR NR_QDRand_01                  ; add factor 2^14 LDA \$03:STA \$FB ; copy result over to seed LDA \$04:STA \$FC LDA \$05:STA \$FD LDA \$06:STA \$FE RTS.NR_QDRand_00 CLC LDA \$03:ADC \$FB:STA \$03 LDA \$04:ADC \$FC:STA \$04 LDA \$05:ADC \$FD:STA \$05 LDA \$06:ADC \$FE:STA \$06 RTS.NR_QDRand_01 CLC LDA \$04:ADC \$FB:STA \$04 LDA \$05:ADC \$FC:STA \$05 LDA \$06:ADC \$FD:STA \$06 RTS.NR_QDRand_02 CLC LDA \$05:ADC \$FB:STA \$05 LDA \$06:ADC \$FC:STA \$06 RTS.NR_QDRand_03 ASL \$FB:ROL \$FC:ROL \$FD:ROL \$FE RTS`

... with R1:=1664525 and R2:=1013904223 this is a single instruction in ARM machine language: MLA R0,R1,R0,R2

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

### Re: Making a random number in Assembly

Mike wrote:
Kakemoms wrote:Its a good one, the Lehmer method, but for me a period of 65536 is a little short. [...] My method with three 16-bit oscillators will ensure no repetition within a very long series of numbers.

The three 16-bit oscillators will also repeat at the latest after 65536 calls. Possibly earlier, with a period of a lower power of 2. Then the period of all 3 oscillators can only be the lowest common multiply, not bigger than 65536. So you're not better off at the moment.

I see the problem. Its because I define each oscillator as being the same size (e.g. max numbers) which actually translates into the oscillator repeating itself each 65536 round or more often. You can view it as a standing wave in a box in which all the boxes are the same size. The waves have to overlap with a repeating interval that is going to be the same each time one steps through.

An easy solution is to make each oscillator having a different size (e.g. max number) so that they do not repeat in sync. The easiest is to look for overflow in MSB and put zero in the oscillator once this happens.

I agree that multiplying the numbers is not a good idea. I have to think more about that as I want a quicker method than Lehmer.

Edit: I found that using an extractor will improve the randomness so that is a better way to combine several randoms. It may be a way to get a "more" random value that can prevent recurring sequences, but since all timers in the vic are essecially repeating numbers one needs user interaction.
I also have another source for random numbers that I need to test out; the NEOS mouse.

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

### Re: Making a random number in Assembly

Ok, so putting in a Von Neumann extractor should improve the randomness.

There is a loop in the source code (loops around 65536 times) and it is only increasing the "oscillators" for each case. You want to make the number of loops to be based on some random event (user input) to make it really random or just choose some other large arbitrary number to make your own version. The VIA timers and raster line location will oscillate as well, so you may want to alter the step-value in the oscillators by using these to improve "randomness" somewhat (I am not sure this is actually going to help though).

Each 16-bit counter is then extracted to a random number using Von Neumann extraction. The number of bits in this random number is going to be less than 16, so by doing so 3 times (3*16=48), it gives a longer output and will give 24 bits in 50% of the cases and 16 bits in most cases. In the event you get fewer bits, the number will start with some bits from the first oscillator.

Code: Select all

`start        lda     \$9119        sta     randomseed        lda     \$9004        sta     randomseed+1        cmp     \$9004        beq     *-3        lda     \$9118        sta     randomseed+2        jsr     initmult        ldx   #\$ffrndlp1   ldy   #\$ffrndlp2        jsr   randomize        dey        bne   rndlp2        dex        bne   rndlp1           jsr   get16rand        rtsrandomize        ; "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      bcc     noovfl1      lda     #0      sta     randomscnoovfl1        lda     randomosc+2        clc        adc     randomseed+1        sta     randomosc+2        lda     randomosc+3        adc     #0        sta     randomosc+3      bcc     noovfl2      lda     #0      sta     randomscnoovfl2        lda     randomosc+4        clc        adc     randomseed+2        sta     randomosc+4        lda     randomosc+5        adc     #0        sta     randomosc+5      bcc     noovfl3      lda     #0      sta     randomscnoovfl3        rtsget16rand        ldx     randomosc        ldy     randomosc+1      stx   \$2      sty   \$3        jsr    neumannextractor        ldx   randomosc+2        ldy   randomosc+3        jsr   neumannextractor        ldx   randomosc+4        ldy   randomosc+5        jsr   neumannextractor        ldx   \$2        ldy   \$3        rts     ;random number in x & y registerneumannextractor   ; Input X & Y, output in \$2 & \$3      TXA      STA \$4      TYA      ORA \$4      STA \$5      TYA      AND \$4      SEC      SBC \$5exlp1      ASL  ;bit7 to carry      BCC noext      ASL \$4   ;get bit into carry      ROL \$3   ;put carry into \$3      ROL \$2   ;roll over to \$2noext      BNE exlp1      ;A not zero      RTS      ;result in \$3 and \$2randomseed        byte    0,0,0randomosc        word    0,0,0`

This is probably going to be ok for most games, but for encryption it is not going to be good enough unless you base it on some random user event (keys, mouse, joystick). A nice thing with the NEOS mouse driver for Vic-20 has a clock that is not syncronized to Vic-20. In fact its a very unstable clock and can be used for a "random stream" by looking for timing value at which the mouse processor resets the output (around 227 cycles +/-5 cycles).

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

### Re: Making a random number in Assembly

I just had another idea that may work on the Vic-20: Using illegal opcode LAX (\$AB) or XAA (\$8B) that are highly unstable may give random results according to Grahams table. He notes that especially LAX loses bits on the C64.

I have never tested these and one can wonder whether the random result is really random. According to visual6502 the illegal opcodes does not result in some transistor "ping-pong" and that the result may be due to data left on the external buses. If its not repeatable it may anyway have some randomness to it.

Has anyone used these illegal opcodes to do such? It would be interesting to test.

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

### Re: Making a random number in Assembly

the result is neither random, nor quite as unstable as that table says for generating random numbers these opcodes are completely useless

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

### Re: Making a random number in Assembly

In the meantime I managed to implement the QDRand routine from Numerical Recipes, so it returns the 32-bit seed/result as fraction from 0 inclusive to 1 exclusive with the USR() function, just as RND() does. A small demonstration program plots random points in a 160x192 hires screen, where a random value is used twice: as y- and then as x-coordinate. If there is an obvious serial correlation of consecutive values, it easily shows with that kind of test. And unlike the original RND() function, the new USR()-RNG eventually fills up the entire screen:

Code: Select all

`10 FORT=828TO1005:READA:POKET,A:NEXT:POKE1,60:POKE2,311 :12 @ON:@CLR:Y=USR({PI})13 X=Y:Y=USR({PI}):@1,160*X,192*Y:GOTO1314 :15 DATA 169,95,133,101,169,243,133,100,169,110,133,99,169,60,133,98,32,164,3,32,210,316 DATA 32,224,3,32,190,3,32,224,3,32,164,3,32,190,3,32,224,3,32,164,3,32,210,3,32,22417 DATA 3,32,210,3,32,224,3,32,190,3,32,224,3,32,190,3,169,0,133,112,133,102,169,12818 DATA 133,97,165,101,133,139,165,100,133,140,165,99,133,141,165,98,133,142,48,11,919 DATA 128,133,98,169,233,160,3,32,103,216,96,24,165,101,101,139,133,101,165,100,10120 DATA 140,133,100,165,99,101,141,133,99,165,98,101,142,133,98,96,24,165,100,101,13921 DATA 133,100,165,99,101,140,133,99,165,98,101,141,133,98,96,24,165,99,101,139,133,9922 DATA 165,98,101,140,133,98,96,6,139,38,140,38,141,38,142,96,128,128,0,0,023 :24 REM ** USR-RND-DEMO.PRG WRITTEN 2016-03-11 BY MICHAEL KIRCHER`

The routine "constructs" the RNG result directly in the FAC (\$61..\$66 and \$70) and "reuses" the ZP workspace of the original RND() seed (\$8B .. \$8E) to store its own 32-bit seed.

As Knuth wrote: "Random numbers should not be generated with a method chosen at random."
Attachments
usr-rnd-demo.zip

darkatx
Posts: 440
Joined: Wed Feb 04, 2009 2:17 pm

### Re: Making a random number in Assembly

I put it on warp and as I watch Mike's demo it reminds me of a starry night and finally entropy taking over. Fascinating - I was wondering why would you need a 32-bit generator for something like games but this plotter makes me appreciate the reasons why.
Well Done Mike as always!
Learning all the time...

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

### Re: Making a random number in Assembly

groepaz wrote:the result is neither random, nor quite as unstable as that table says for generating random numbers these opcodes are completely useless

Yea, I used the simulator at visual6502.org to confirm that the result was not very straightforward, but very repeatable. As everything else in the digital world..

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

### Re: Making a random number in Assembly

that simulator doesnt simulate those opcodes correctly either )

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

### Re: Making a random number in Assembly

groepaz wrote:that simulator doesnt simulate those opcodes correctly either )

Wot? But its a transistor level simulation, how can it be wrong?

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

### Re: Making a random number in Assembly

well, its actually not quite "transistor level" - thats the problem.... the transistors are not actually modelled in an analog way, the netlist nodes are still "digital" (more or less). thats ok for the regular opcodes, however for a bunch of the illegal ones that doesnt work, because their result depend on various strange analog side effects (which are not simulated).

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

### Re: Making a random number in Assembly

Hi

I have been testing this way of randomizing and since its a serial function, I have chosen to use a random seed (based on rasterline and VIA) and calling the LCG as many times as the seed number before starting to fetch "random" numbers.

This is a good way to get a random start, but it takes too long to call the LCG to do it more than around 1000 times. E.g. the start "random" number will be repeating around 1/1000.

I am thinking of changing the seed value of the random function to do this faster, but according to LCG description, its easy to get a less than random result if I do this.

Any ideas on how to properly initialize this to not get the same series over and over again?