Hello everbody,

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



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:



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:

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.

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

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:



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

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.

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

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

though nothing complicated, this is the generic version:



and here my version in 6502 assembler.



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

\twh

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.



Actually,





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



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

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:



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.

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.

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

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:



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:



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:



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



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:



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.