random number in assembly

[eflake]

Any thoughts, comments, or suggestions on this, took me a couple of hours to tweak this out looking through google one topic in this forum.

 

	org $1000
icl "hardware.s"

rnd = $C6
     
top
  lda $D20A ;read 53770 location
  sta rnd  ;address holding random number

getrnd  lsr rnd  ;shift value down
  lda rnd        ;load to acc
  cmp #$40       ;compare with immediate hex 40
  bcs getrnd     ;branch if carry is set (greater than condition)
  jmp top        ;get a new random number

 

[TGB1718]

I think this does much the same 

 

   org $1000
icl "hardware.s"

rnd = $C6
     
top
  lda $D20A ;read 53770 location

  and #$3F

  sta rnd

  jmp top

 

 

[eflake]

thanks, purpose is to limit it using the cmp #$40 or even #6 for dice. Is there a cycle saving shortcut for that

[TGB1718]

If you want a number for dice between 1 and 6, I think this is probably quickest

 

    org $1000

    rnd=$c6

  jsr random

  etc...

 

random lda $d20a

  and #7

  beq random

  cmp #7

  beq random

  sta rnd

  rts

[damosan]

Here's what I used in my assembly language roguelike project.  It's not as efficient as it should be (see dice2 loop to calculate the modulus) but it works. 

 

Usage:

ldx	#3
ldy	#6
jsr	dice		
sta	strength	;;; generate player's strength

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; dice - rolls X dice of Y sides storing result in accum.  TRND & TSIDES
;;		are byte variables defined elsewhere.
;;
dice	lda	#0
		sta	trnd		; temp result bucket
		sty	tsides		; number of sides on the dice
dice1	lda	RANDOM		; get random number from hardware
		sec
dice2	sbc	tsides		; subtract the number of sides
		bcs	dice2		; carry set?  Subtract again!
		adc	tsides		; now accum = n mod m (0 .. m-1)
		clc
		adc	trnd		; add accum to trnd
		sta	trnd		; store it back to trnd
		inc	trnd		; increment trnd by one so n mod m range is (1 .. m)
		dex				; another dice?
		bne	dice1		; yup, do it again!
		lda	trnd		; store temp random to accum and return
		rts

 

[Wrathchild]

14 minutes ago, damosan said:

clc 
adc trnd ; add accum to trnd 
sta trnd ; store it back to trnd 
inc trnd ; increment trnd by one so n mod m range is (1 .. m)

 

small optimization

sec ; increment by one so n mod m range is (1 .. m)
adc trnd ; add accum to trnd 
sta trnd ; store it back to trnd

 

[damosan]

Thanks WrathChild.

[flashjazzcat]

That will make the final 'lda trnd' redundant as well, since the desired value is pre-loaded into A when you're done.

[damosan]

2 minutes ago, flashjazzcat said:

That will make the final 'lda trnd' redundant as well, since the desired value is pre-loaded into A when you're done.

Tweaked.

[thorfdbg]

8 hours ago, damosan said:

Here's what I used in my assembly language roguelike project.  It's not as efficient as it should be (see dice2 loop to calculate the modulus) but it works. 

Not really. If the number of sides does not divide 256, the output will not be equi-distributed, so it only simulates a loaded dice.

[damosan]

15 hours ago, thorfdbg said:

Not really. If the number of sides does not divide 256, the output will not be equi-distributed, so it only simulates a loaded dice.

 

Then fix it.  It works well enough for the standard d4, d6, d8, d10, d12 dice it was meant to support.

[thorfdbg]

7 hours ago, damosan said:

 

Then fix it.  It works well enough for the standard d4, d6, d8, d10, d12 dice it was meant to support.

Not really.  To illustrate the problem, consider that the random number generator generates numbers between 0 and 7 (3 bit), and consider you simulate a D6. Then, the numbers 0 and 6 generate a 1, 1 and 7 generate a 2, but there is only a probability of 1/8 for all other sides of the dice. The unbalance is less extreme for more bits, but it is still present.

 

The fix for this is the "rejection trick". That is, subdivide the total output range of the input random number generator into equally sized sets, and a remainder set, and whenever you get an output in the remainder set, reject it and run the input random number generator again. This, provably, simulates a fair dice, all provided the input number generator has a uniform distribution.

For example, you can fix your algorithm for a D6 by rejecting all numbers >= 252 (42*6) and then follow the same program flow.

 

For reference, see for example "Donald Knuth, The Art of Programming, Volume II: Numerical and Semi-Numerical Algorithms". But, again, the argument is quite simple, and so is the fix.

 

 

[solo/ng]

in our Lynx productions Laoo did this:
 

.proc Random
RndStore equ *+1
eor #42 ;answer to life the universe and everything
rol
eor LYNX.VCOUNT_COUNT
sta RndStore
rts
.endp

it could be easly chagned for other machines (just adapt the line with 'eor').

usage:

jmp random

A = the pseudo-random number

its simple and pretty decent (used it Lynx Quest and demos). Could be better (n-passes) but the speed was most important here.

Edited May 12, 2022 by solo/ng

[damosan]

4 hours ago, thorfdbg said:

For example, you can fix your algorithm for a D6 by rejecting all numbers >= 252 (42*6) and then follow the same program flow.

If I'm understanding you correctly...

 

d4 = No remainder set

d6 = 252

d8 = No remainder set

d10 = 250

d12 = 252

d20 = 240

d100 = 200

 

 

[rudla]

You can fill 256 byte table with numbers from min to max (for example for dice it could be 1,2,3,4,5,6,1,2,3,4,5,6,...).

Then you do

 

ldx $d20a

lda random_table,x

 

It will be slightly biased toward 1,2,3 and four, as the 256 is not divisible by 6.

Very slightly though.

 

 

[+gnusto]

If you're interested this is an LSFR implementation : https://github.com/bbbradsmith/prng_6502

 

However you need to use the 16bit wide version to not repeat sequences very quickly, so it would be slow for highly repetitive use.