Assembler Random number usage

[Grevle]

Still learning about assembler i wonder whats the best or most common way of doing the Basic Equalent to have 3 random number choosen.. 1, 2 or 3. In Mac 65 Assembler.

 

In Turbo Basic XL this is very simply just specify directly X=Rand (3).

 

So in mac 65 assembler, what would the best way.

 

in Assembler the Random number generator returns a number between 0 and 255, So if one divide 255 by 3 then you get 85, Is then to have assembler program behave in this way:

 

IF number returned is between 0 and 85 then select 1. IF number returned is between 85 and 170 then select 2. If number returned is between 170 and 255 then select 3.

This would be have to be done by using LDX, some CPX, BCC and BCS ofcoarse.

 

 

This Equales a 3 nr RND select in basic, A direct and fast way of doing it, Is this the common way or are there more clever way to do this ?, wihout to mutch complicated math i hope....

 

Thanks.

Edited August 12, 2016 by Grevle

[RevEng]

What you're proposing would work for lower ranges, but uses a lot of comparisons when you need a value (for example) between 1 and 9. That wastes ROM and cycles.

 

Another approach is to take the random and mask off bits that get you close to your number. (ie. the nearest power of 2 that's greater than your desired range, less one.) If the masked random is larger than your desired range, branch back and grab another.

 

For generating a value between 0 and 2 (better to use 0-2 instead of 1-3) you take the random number and mask off all but the lowest 2 bits with "and #3", which will give you a random value from 0-3. If the value is 3, branch back and grab another random.

 

When you start using this approach, you'll likely find a lot of cases where the power-of-2 random will work just as well for your game, which means you can eliminate the branch-back.

[Rybags]

You can read RANDOM then use AND to reduce to a lower power of 2. But still that doesn't help greatly when you're after a specific range that's not catered for like your case.

What you could do is read RANDOM multiple times to get your number (go additive) or read it once, mask out unwanted bits and reject values that are out of range.

e.g. additive method, has to rerun if it gets a zero:

; build a random number value 1 to 3.
getrand
  lda random
  and #1
  sta work1
  lda random
  and #2
  ora work1
  beq getrand ; reject if zero
  rts

e.g. mask out and reject out of range:

getrnd
  lda random
  and #3 ; mask value will only include values 0-3
  beq getrnd ; reject zero value
  cmp #4
  bcs getrnd ; reject value too large.
; This won't happen but you'd want this test e.g. if doing different range like 1-5 where the used mask value would be 7.
  rts

When generating RND for a given range it's probably easier to just start at 0, then add in the low range value once you've got the number.

Edited August 12, 2016 by Rybags

[phoenixdownita]

You can refine by not needing branch for a few tries.

In the example you gave and with the technique by RevEng if after you grabbed the lower 2 bits you hit 11, then you can grab the next 2 bits and so on until exhaustion (that gives you 4 trials in 1 generated random byte, that is there is only 1 chance in 256 that you need a new random number and that is when all bits are 1).

Depending if it's faster to grab a random number rather than shift and mask this approach can be worthy, the max you can get this way is 4 bits though (2 trials with a single random byte), as soon as you need more than 4 bits to represent your number then you need a new random for a new trial anyway.

 

A different approach is to fill a table [256 entries] with the numbers you want, like 1,2,3,1,2,3,1,2,3 etc....etc... and use the random value as an index into it.

The result is going to be biased, if you can live with that then you're done but if not notice that the last run of numbers won't be complete like 1 or 1,2 in your case, that means the last few positions of the table are unusable per se and require a new random gen if the index falls there. [it is wasteful in terms of space obviously and can be optimized further by halving the size of the table and shift right the random value (basically halving the index range treating odds and even the same way), you can shift twice and have only 64 entries etc.. depending on needed range and tolerance to regen new random with higher probability]

[Dmitry]

This is just a thought, and certainly correct me if I'm wrong, but I would use a modulo.

 

Divide the random number by 3, and the modulo is 0, 1, or 2.

 

Now 6502 doesn't have div and mod but I'd do a google search, such as "mod and div implemented in 6502 asm" and then grabbing someone's code and pasting it mine.

What I'm usually going for is readable code. I concentrate on timing critical stuff in certain parts, but usually my random number needs aren't part of a critical timing loop.

[phoenixdownita]

This is just a thought, and certainly correct me if I'm wrong, but I would use a modulo.

 

Divide the random number by 3, and the modulo is 0, 1, or 2.

 

Now 6502 doesn't have div and mod but I'd do a google search, such as "mod and div implemented in 6502 asm" and then grabbing someone's code and pasting it mine.

What I'm usually going for is readable code. I concentrate on timing critical stuff in certain parts, but usually my random number needs aren't part of a critical timing loop.

 

https://gist.github.com/hausdorff/5993556

 

It for sure works but it is the long way around and it's somewhat linear on the magnitude of the value.

If the random is 223 for example (74 x 3 + 1) it takes the mod algo 75 steps (sbc and bcs) to return 1 (for the case that we do mod 3 as in the OP example).... but as you said at least it's readable (but a good comment would do for any other solution and keep readability).

 

On a side note the table approach allows to "cheat" where needed, that is to say approximate a non uniform distribution.

Take a 6 sided dice, the table would be 1,2,3,4,5,6,1,2,3,4,5,6 ..... but let's assume we want 1 to be twice as likely to come up on the dice then the table becomes 1,1,2,3,4,5,6,1,1,2,3,4,5,6 ...... you can basically shape the distribution the way you want (well up to 1/256 increments).

I know it is off topic and not what the OP asked, just thought of reporting it here.

[Grevle]

Ok thank you . I will get it to work one way or another....

[pirx]

one important detail to remember - always introduce some kind of user input delay, otherwise you will be getting the same value sequences when using emulators. both real hardware and emulation are deterministic, on the real hardware various delays in I/O make it nicely random, but on emulators you will be getting the same exact sequences all the time.

[MaPa]

one important detail to remember - always introduce some kind of user input delay, otherwise you will be getting the same value sequences when using emulators. both real hardware and emulation are deterministic, on the real hardware various delays in I/O make it nicely random, but on emulators you will be getting the same exact sequences all the time.

 

Depends on emulator.. Altirra will do the same sequence, Atari800Win does not AFAIK and other I don't know.

[Dmitry]

https://gist.github.com/hausdorff/5993556

 

It for sure works but it is the long way around and it's somewhat linear on the magnitude of the value.

If the random is 223 for example (74 x 3 + 1) it takes the mod algo 75 steps (sbc and bcs) to return 1 (for the case that we do mod 3 as in the OP example).... but as you said at least it's readable (but a good comment would do for any other solution and keep readability).

 

On a side note the table approach allows to "cheat" where needed, that is to say approximate a non uniform distribution.

Take a 6 sided dice, the table would be 1,2,3,4,5,6,1,2,3,4,5,6 ..... but let's assume we want 1 to be twice as likely to come up on the dice then the table becomes 1,1,2,3,4,5,6,1,1,2,3,4,5,6 ...... you can basically shape the distribution the way you want (well up to 1/256 increments).

I know it is off topic and not what the OP asked, just thought of reporting it here.

 

 

I don't dispute the math, I just think discussing it further is fun

If you've got the cycles to burn, then it's a matter of personal preference. That's a big *if*, but it often occurs in my code that random numbers can be setup in advance and not go in the game loop. Nothing is faster inside the game loop than already having the number in some memory location.

I prefer a couple of lines of code. 75 steps is nothing - blink of an eye.

I know I'm speaking heresy, but anyway....enjoyed the topic.

[Rybags]

Another alternative - if you have cycles to burn, do it how Basic does it. Read RANDOM twice to give a 16 bit integer. Use FP routines to divide that by 65536. You will be left with a fractional result >0 <1. Then use FP once again to multiply it to fall within the range you want.

Note of course you'd be burning the best part of a frame or more worth of CPU cycles.

 

But realistically, my method would be to mask off unwanted bits and either retry or reassign values that aren't valid. Table method OK too but I wouldn't waste lots of memory on it.

[+Eyvind Bernhardsen]

This is just a thought, and certainly correct me if I'm wrong, but I would use a modulo.

 

Divide the random number by 3, and the modulo is 0, 1, or 2.

 

That won't give you a truly random number. It's a small difference in this specific case: the probability of a 0 will be 86/256 while 1 and 2 will be 85/256.

 

If you want a random number between 0-99, though, numbers 0-55 will have probability 3/256 each, while 56-99 are each a third less likely at 2/256.

[drac030]

Another alternative - if you have cycles to burn, do it how Basic does it. Read RANDOM twice to give a 16 bit integer. Use FP routines to divide that by 65536. You will be left with a fractional result >0 <1. Then use FP once again to multiply it to fall within the range you want.

Note of course you'd be burning the best part of a frame or more worth of CPU cycles.

One could also fill the 5-byte mantissa of an FP number with decimal digits read from the random number generator, then adjust the exponent accordingly. This at least saves the division.

 

This method is used by TBXL, it reads the RANDOM in a loop, gets low nibble, saves it into the FP number, then gets the high nibble, saves it as well, then goes to the next byte of the mantissa (of course skipping every value that exceeds the 0-9 range).

 

Then it sets the exponent to -1 ($3F) and voila, there is RND() result without a division.

Edited August 12, 2016 by drac030

[phoenixdownita]

 

That won't give you a truly random number. It's a small difference in this specific case: the probability of a 0 will be 86/256 while 1 and 2 will be 85/256.

 

If you want a random number between 0-99, though, numbers 0-55 will have probability 3/256 each, while 56-99 are each a third less likely at 2/256.

Assuming Random (the original generator) is truly random the modulo gives a truly random number, but I understand what you meant to say, and you are right that module alone will not give a uniformly distributed random number due to the fact that the range of the random has a tail that generates only a portion of the wanted range thus increasing its likelihood (like you showed in your example 0-99) that is to say the range of the random is not an exact multiple of the wanted range.

 

It is relatively easily fixed by making sure to discard all values that are higher than a certain number (in the 0-99 case anything higher than 199 is the cause of the bias) and get another RND.

[MaPa]

LOL... as random pokey register is not random anyway, this discussion about "truly" random generating is a little bit "pointless" IMHO

 

I can't think out some case, besides some mathematical exercises, where the small difference in randomness by using tables or so would be so noticeable that it would not be acceptable.

Edited August 12, 2016 by MaPa

[phoenixdownita]

LOL... as random pokey register is not random anyway, this discussion about "truly" random generating is a little bit "pointless" IMHO

 

I can't think out some case, besides some mathematical exercises, where the small difference in randomness by using tables or so would be so noticeable that it would not be acceptable.

Even if it is true, way to kill the mood of the thread

[Grevle]

Here is what i did. here is a 6 number random generator. only needs to read the random generator once and then i store the wanted value in the BANDY equate. this works well in my program. maybe not the most space saving methode but simple and straight forward. The RTS will send the program back to wherever i JSR from and continue my program.

 

GETR

LDX 53770 ; GET RANDOM NUMBER
CPX #42
BCC SET1
CPX #84
BCC SET2
CPX #126
BCC SET3
CPX #168
BCC SET4
CPX #210
BCC SET5
JMP SET6

SET1
LDX #61
STX BANDY
RTS
SET2
LDX #81
STX BANDY
RTS
SET3
LDX #100
STX BANDY
RTS
SET4
LDX #119
STX BANDY
RTS
SET5 LDX #139
STX BANDY
RTS
SET6
LDX #159
STX BANDY
RTS

Edited August 15, 2016 by Grevle

[Rybags]

You could probably tighten it up a bit, use the Carry after compares to generate the result, e.g.

 

 

  lda #1
  ldx $D20A
  cpx #42
  adc #0
  cpx #84
  adc #0
  cpx #126
  adc #0
  cpx #168
  adc #0
  cpx #210 
  adc #0
  rts

 

That will give value from 1-6 returned in A.

 

Another method for a small range, you could just add up bits in the value as you shift them out.

 

 

  lda $D20A
  sta rnd
  lda #1
  ldx #6 ; generate a range of 1-7
getrnd  lsr rnd
  adc #0 ; shift into Carry, add to result
  dex
  bne getrnd
  rts