Making a random number in Assembly

Basic and Machine Language

Moderator: Moderators

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: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 produced 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.
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 »

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.
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 »

OK. Will do.
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 »

[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_QDRand_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 :mrgreen:
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:
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: 740
Joined: Sun Feb 15, 2015 8:45 am

Re: Making a random number in Assembly

Post by Kakemoms »

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   #$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
	   bcc     noovfl1
	   lda     #0
	   sta     randomsc
noovfl1
        lda     randomosc+2
        clc
        adc     randomseed+1
        sta     randomosc+2
        lda     randomosc+3
        adc     #0
        sta     randomosc+3
	   bcc     noovfl2
	   lda     #0
	   sta     randomsc
noovfl2
        lda     randomosc+4
        clc
        adc     randomseed+2
        sta     randomosc+4
        lda     randomosc+5
        adc     #0
        sta     randomosc+5
	   bcc     noovfl3
	   lda     #0
	   sta     randomsc
noovfl3
        rts

get16rand
        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 register


neumannextractor	; Input X & Y, output in $2 & $3

		TXA
		STA $4
		TYA
		ORA $4
		STA $5
		TYA
		AND $4
		SEC
		SBC $5
exlp1
		ASL  ;bit7 to carry
		BCC noext
		ASL $4	;get bit into carry
		ROL $3	;put carry into $3
		ROL $2	;roll over to $2
noext
		BNE exlp1		;A not zero
		RTS		;result in $3 and $2



randomseed
        byte    0,0,0
randomosc
        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: 740
Joined: Sun Feb 15, 2015 8:45 am

Re: Making a random number in Assembly

Post by Kakemoms »

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 Scientist
Posts: 1180
Joined: Wed Aug 25, 2010 5:30 pm

Re: Making a random number in Assembly

Post by groepaz »

the result is neither random, nor quite as unstable as that table says :) for generating random numbers these opcodes are completely useless
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 »

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

Code: Select all

10 FORT=828TO1005:READA:POKET,A:NEXT:POKE1,60:POKE2,3
11 :
12 @ON:@CLR:Y=USR({PI})
13 X=Y:Y=USR({PI}):@1,160*X,192*Y:GOTO13
14 :
15 DATA 169,95,133,101,169,243,133,100,169,110,133,99,169,60,133,98,32,164,3,32,210,3
16 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,224
17 DATA 3,32,210,3,32,224,3,32,190,3,32,224,3,32,190,3,169,0,133,112,133,102,169,128
18 DATA 133,97,165,101,133,139,165,100,133,140,165,99,133,141,165,98,133,142,48,11,9
19 DATA 128,133,98,169,233,160,3,32,103,216,96,24,165,101,101,139,133,101,165,100,101
20 DATA 140,133,100,165,99,101,141,133,99,165,98,101,142,133,98,96,24,165,100,101,139
21 DATA 133,100,165,99,101,140,133,99,165,98,101,141,133,98,96,24,165,99,101,139,133,99
22 DATA 165,98,101,140,133,98,96,6,139,38,140,38,141,38,142,96,128,128,0,0,0
23 :
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." :)
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 »

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: 740
Joined: Sun Feb 15, 2015 8:45 am

Re: Making a random number in Assembly

Post by Kakemoms »

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 Scientist
Posts: 1180
Joined: Wed Aug 25, 2010 5:30 pm

Re: Making a random number in Assembly

Post by groepaz »

that simulator doesnt simulate those opcodes correctly either :o)
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:that simulator doesnt simulate those opcodes correctly either :o)
Wot? But its a transistor level simulation, how can it be wrong?
groepaz
Vic 20 Scientist
Posts: 1180
Joined: Wed Aug 25, 2010 5:30 pm

Re: Making a random number in Assembly

Post by groepaz »

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).
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 »

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?
Post Reply