rand() % 192

[twh1st]

Hello everbody,

Obviously I'm new to 6502 assembler. Maybe all too simple, but how do I translate this C-style line into 6502:

Code: Select all

 
int i = rand() % 192

let's say I am able to produce a random 8bit number. I want to limit the max value of the randomly generated number to 192. So everything between 0-192 would be fine for me.

My first approach was something like this:

Code: Select all

 
rand sta limit   ; save the upper limit
rnd  lda random  ; get the hardware random number
     cmp limit   ; check against the limit
     bcs rnd     ; loop back until it is within the limit
     rts 

But this is not really like translating "%"-Operator. any better solutions?

\twh

[Thowllly]

twh1st wrote:

Hello everbody,

Obviously I'm new to 6502 assembler. Maybe all too simple, but how do I translate this C-style line into 6502:

Code: Select all

 
int i = rand() % 192

let's say I am able to produce a random 8bit number. I want to limit the max value of the randomly generated number to 192. So everything between 0-192 would be fine for me.

My first approach was something like this:

Code: Select all

 
rand sta limit   ; save the upper limit
rnd  lda random  ; get the hardware random number
     cmp limit   ; check against the limit
     bcs rnd     ; loop back until it is within the limit
     rts 

But this is not really like translating "%"-Operator. any better solutions?

\twh

First of all, %192 will limit the range to 0-191, not 0 to 192, I think. Also, if you do that, the numbers in the range 0 to 63 are twice as likely to come up as the numbers in the range 64 to 191. But if thats really what you want you can do it like this:

Code: Select all

    lda random
    cmp limit
    bcc -
    sbc limit
-   rts

[BitWise]

If your 8 bit random number generator produces a good distribution then your first approach would be pretty good although each execution would take an unpredicately length of time to complete. It avoids the problem that Thowilly points out with the mod operator.

To get a good 0-191 ranged random number you really need a bigger random value to start with. If you had 16-bits to apply the mod to then you would still get the remainder issue but instead of the probability being and extra 64/256 in favour of a 0-63 value it would become an extra 64/65536 which is probably not statistically significant for most applications.

[twh1st]

Thowllly wrote:

First of all, %192 will limit the range to 0-191, not 0 to 192, I think. Also, if you do that, the numbers in the range 0 to 63 are twice as likely to come up as the numbers in the range 64 to 191. But if thats really what you want you can do it like this:

Code: Select all

    lda random
    cmp limit
    bcc -
    sbc limit
-   rts

mhm. I don't understand fully why I should get twice as likely numbers in between 0-63.

191 or 192 doesn't matter. What I really want to do is to generate a random number within a margin. So let's say I want to get a number within 32 - 160. In this case I would do in C this:

Code: Select all

int i = 32+rand()%160

Calculating the lower border is obviously not an issue as the 6502 easily can handle addition/subtraction. What I am missing is the modulo and div operator.

\thomas

[BitWise]

Quote:

mhm. I don't understand fully why I should get twice as likely numbers in between 0-63.

If you mod a byte value 0-255 with 192 then some values will mod to the same output value. For example 0 and 192, will give the result 0. 1 and 193 will give 1 etc. The values 64-191 will only be generated if the original value was 64-191. So given that two ways to generate 0-63 and only one to generate 64-191 a lower number has twice the probabilty of being generated than a higher one.

The expression 32 + rand () % 160 generates a number in the range 32 to 191 and not 32 to 160.

[twh1st]

BitWise wrote:

Quote:

The expression 32 + rand () % 160 generates a number in the range 32 to 191 and not 32 to 160.

true that. I was wrong with my example. Thx for the correction

though nothing complicated, this is the generic version:

Code: Select all

r = [rand() % (t-b)] + b

and here my version in 6502 assembler.

Code: Select all

; --------------------------------------
; subroutine rand
; Get a random number from the value passed in Y to the value passed in ACCUM.
; result is stored in A

bottom  dta 0
limit  dta 0

rand   sty bottom
        sec
        sbc bottom
        sta limit

rnd    lda     random  ; get the hardware random number
        cmp     limit   ; check against the limit
        bcs     rnd     ; loop back until it is within the limit
        clc
        adc bottom
        rts 

I still have a bad feeling regarding the unpredictable count of iterations...

\twh

[kc5tja]

twh1st wrote:

mhm. I don't understand fully why I should get twice as likely numbers in between 0-63.

Assume that the random function generator returns an even spread of numbers from 0..255 inclusive. If that number thus returned is 192 or greater, then 192 is subtracted from it, leaving you with a number that is, at best (255-192=)63. Therefore, 192..255 will tend to "alias" around to 0..63.

Quote:

191 or 192 doesn't matter. What I really want to do is to generate a random number within a margin. So let's say I want to get a number within 32 - 160. In this case I would do in C this:

Code: Select all

int i = 32+rand()%160

Actually,

Code: Select all

int i = 32+(rand() % 128);

If you are willing to waste a few extra cycles, you can do something like this:

Code: Select all

again:
    jsr rand
    cmp #192
    bcs again
    clc
    adc #32

The idea here is, if the random number is outside your accepted range, just take another number -- eventually you're bound to get one that is inside your range, and is a whole lot cheaper than implementing a modulo that is not a power of 2 (as you point out, you'll need to write a software division routine to do it).

[John West]

kc5tja wrote:

(as you point out, you'll need to write a software division routine to do it).

If the modulus is a constant, you don't need a general division routine. Calculating mod directly can be easier.

It's easiest for numbers that are the difference between a large and a small power of two. For example (Christopher will recognize this one, if he's reading), mod of a number between 0 and 1023 by 120:

Code: Select all

x % 120= d*2^9 + c*2^8 + b*2^7 + a
(d, c, b are 0 or 1.  a is between 0 and 63)
= (d*(2^9 % 120) + c*(2^8 % 120) + b*(2^7 % 120) + a%120) % 120
= (d*32 + c*16 + b*8 + a) % 120
= ((x>>4)&56 + x&127) % 120

You've still got a mod of 120 at the end, but since the range has been reduced so much, it can be done with one compare and subtract.

In general for x mod y: start with i = 0, a = 1 and total = 0. If bit i of x is 1, add a to total. If total is greater than y, subtract y. Double a. If a is greater than y, subtract y. Increment i. Repeat until you run out of bits in x. The result is in total.

If y is less than 256, you don't need to do any arithmetic with more than 9 bits (you can keep the 9th in the carry flag). The size of x doesn't matter.

[kc5tja]

Your math completely escapes me. I like to think I'm good at algebra, but you're manipulating the equations in a manner most inconsistent with the rules of algebra that I'm familiar with.

Also, it would seem to me that the size of x most definitely does matter; if x is a 24-bit number, for example, you'll be "comparing and subtracting" quite often. The algorithm you posted is essentially a software divide routine using shift-and-subtract.

[Kallikak]

If your rand() implementation is not too expensive, I'd also suggest just looping until acceptable (though if the range is narrow, consider the best 'n' bits only - e.g. the high bits if you're using a simple LCG algorithm).

The % operator is fundamentally a division, and that's slow on the 6502. If you really want to divide by 120 say, you can use the fact that 1/120 = 2^-7 + 2^-11 + 2^-15... and do it as shifts and sums, but to get the remainder you'd then have to multiply your answer by 120 and be careful of roundoff errors etc.

You could also do a simple approximation using the closest power of two followed by a correction using repeated addition or subtraction as required. For example, to calculate 5656 / 120, do 5656/128 = 44 (easy). Then 44 * 120 = 44 * (2^3 + 2^4 + 2^5 + 2^6) = 5280 (not too hard). The difference is 376, so subtract 120 from this 3 times and you've got 16 which is 5656 mod 16. (You've also got 47 = 5656 / 120 if you want it.) This approach is not too hard to generalise either.

Ken

[dclxvi]

John West wrote:

Code: Select all

x % 120= d*2^9 + c*2^8 + b*2^7 + a
(d, c, b are 0 or 1.  a is between 0 and 63)
= (d*(2^9 % 120) + c*(2^8 % 120) + b*(2^7 % 120) + a%120) % 120
= (d*32 + c*16 + b*8 + a) % 120
= ((x>>4)&56 + x&127) % 120

Since this hasn't been elaborated upon yet, here's what's happening. First, there is a minor typo -- "a" ranges from 0 to 127, rather than 0 to 63. Anyway, to compute:

result = x % 120

where

x = u * 128 + a

i.e. a is the lower 7 bits of x and u is the upper bits.

result = (u * 128 + a) % 120

which is the same as:

result = (u * (120 + 8) + a) % 120

which is the same as:

result = (u * 120 + u * 8 + a) % 120

since u * 120 is a multiple of 120 it won't affect the result, so that term can be discarded, leaving:

result = (u * 8 + a) % 120

So far, none of this depends on how many bits u consists of. In the example, x ranged from 0 to 1023, so u is 3 bits.

u = (x >> 7) & 7, so u * 8 is the same as (x >> 4) & (7 << 3), and a = (x & 127), so the formula can be written as:

result = ((x >> 4) & 56 + x & 127) % 120

since u can be at most 7 and a can be at most 127, u * 8 + a can be at most 183, which is less than 2 * 120, so only one comparison to 120 (and subtracting 120 if greater than or equal) is needed to compute the final % 120. In other words, the calculation can be performed in two steps:

1. result = (x >> 4) & 56 + x & 127
2. if (result >= 120) result = result - 120

This is much, much faster than a general purpose shift-compare-subtract division routine.

Different moduli give different optimized formulas though, some of which are smoother than others. (This is analogous to multiplication for a specific multiplier, where e.g. 10 * x can be quickly computed as x * 8 + x * 2 (or usually, as (x * 4 + x) * 2), and 255 * x = 256 * x - x, but 163 * x (163 = $A3), while not bad, isn't as smooth a case as the other two.) For example, (hi * 256 + lo) % 255, where hi and lo both range from 0 to 255, is:

result = (256 * hi + lo) % 255
result = (255 * hi + hi + lo) % 255
result = (hi + lo) % 255

hi + lo can be at most 510, which isn't less than 2 * 255 ... but, if the sum is split up as follows:

hi + lo = sumh * 256 + suml

where sumh is the upper bit (i.e. bit 8) of the sum and suml is the lower 8 bits, so:

result = (sumh * 256 + suml) % 255
result = (sumh * 255 + sumh + suml) % 255
result = (sumh + suml) % 255

sumh + suml will be at most 255 (since 510 is the maximum sum, when sumh is 1, suml can be at most 254) and this is less than 2 * 255, so only a single compare and subtract if greater than or equal to is necessary. In 6502 assembly, this is:

Code: Select all

     CLC
     LDA HI
     ADC LO
     ADC #0   ; add the high bit of sum
     CMP #$FF ; subtract 255 if greater than 255
     BCC SKIP
     SBC #$FF ; note that carry known to be set beforehand
SKIP

In fact, this can be simplified even further. Consider the result of SBC #$FF, which is A - $FF if the carry was set (beforehand), and A - $FF - 1 if the carry was clear; A - $FF - 1 is A - $100, which leaves A the same and clears the carry. So the BCC is completely unnecessary, and can be discarded, leaving:

Code: Select all

     CLC
     LDA HI
     ADC LO
     ADC #0   ; add the high bit of sum
     CMP #$FF ; subtract 255 if greater than 255
     SBC #$FF

It seems like it ought to be possible to optimize that even further, especially since the carry out of the ADC #0 is not used by the subsequent CMP #$FF instruction. In fact it is possible. After the ADC LO instruction, the accumulator and carry will be:

Code: Select all

1. A = 0 to 254, C = 0 if HI + LO was 0 to 254
2. A = 255,      C = 0 if HI + LO was 255
3. A = 0 to 253, C = 1 if HI + LO was 256 to 509
4. A = 254,      C = 1 if HI + LO was 510

If the ADC LO instruction is followed by a ADC #1 instruction, A and C (after the ADC #1 instruction) will be:

Code: Select all

1. A = 1 to 255, C = 0 if HI + LO was 0 to 254
2. A = 0,        C = 1 if HI + LO was 255
3. A = 2 to 255, C = 0 if HI + LO was 256 to 509
4. A = 0,        C = 1 if HI + LO was 510

So all that is necessary is to subtract 1 from A in cases 1 and 3, or in other words, subtract 1 when the carry is 0. This can be done with a SBC #0 instruction, which subtracts 0 when C = 1 and subtracts 1 when C = 0. So the code becomes:

Code: Select all

     CLC
     LDA HI
     ADC LO
     ADC #1
     SBC #0

That's a 16-bit mod 255 calculation in only 5 instructions, without a loop!

Another example is mod 65521 (used in Adler-32 checksum calculations). For a * 65536 + b (where b ranges from 0 to 65535):

result = (a * 65536 + b) % 65521
result = (a * 65521 + 15 * a + b) % 65521
result = (15 * a + b) % 65521
result = (16 * a - a + b) % 65521

which is a faster computation, and again, the lower 16 bits of 16 * a - a + b can be split off to reduce it further.

Basically, this mod optimization technique is the same principle as the old "a number is divisible by 9 if its digits sum to 9" trick.