# Modulus arithmetic on the 6502

I have a very simple problem with is turning out to be surprisingly complex to solve.

I wish to add two bytes using modulus arithmetic, where the modulus is known at compile time. e.g. given modulus 5, 3+3 = 1. The specific number I have currently for the modulus is 201, but that might change in the future.

On fast computers, this is just `(x+y) % modulus`. Except, this requires extending the intermediate values to words, to avoid overflow, and then doing a division, which I'd very much like to avoid (this is going to be happening rather a lot). The other option is to try and redefine my problem so that `modulus` is a power of two, and then just masking the result... but I can't do that in this case.

Are there any cunning tricks for doing this on the 6502 which someone can suggest?

• Back in the day, circa 1981, I could have whipped this out in 6502 assembly in a few minutes. But it's been a while. Interesting problem, I'm looking forward to seeing a solution. – jwh20 Dec 12 '20 at 23:50
• While writing my answer (it's simply too tempting to answer) I started to question if this is really fit for RC.SE question at all? It's a generic question about doing fast modulo calculation in a restricted environment. All tie in to RC.SE is mentioning a 6502 as target, which alone might not be enough. Or is there a background that would make it relevant? If yes, would you mind to include it to the question? – Raffzahn Dec 13 '20 at 0:38
• Will the two numbers to be added are already within the modulus range? Or could it be that `x` is larger than the modulus in the first place? – Peter B. Dec 13 '20 at 2:40
• Yes, both `x` and `y` are guaranteed to be below `modulus` --- that's guaranteed by the nature of modulus arithmetic; I should have made that clearer. – David Given Dec 13 '20 at 9:47
• @Raffzahn there is a meta question about what kinds of programming questions are on topic here. – OmarL Dec 13 '20 at 10:55

Here's a shorter solution than wizzwizz4's:

``````  SEC
LDA x
SBC modulus
BCS end
end:
``````

The idea is to bias the inputs so that the addition overflows just when the modulus needs to be subtracted.

This requires x < modulus. If y < modulus then the result will be less than modulus, otherwise it may be any value like y. The carry will always be set at the end which may be useful.

• After sleeping on it I realised that biasing the inputs is obviously the simplest approach. But, I was going to add `256-modulus`. Subtracting it instead allows clever use of the carry. This works fine, and I don't think it gets much cheaper than this. Thanks! – David Given Dec 13 '20 at 12:21
• This technique is especially useful for modulus `< 128`; it pretty much halves the number of instructions you need. If I can wrap my head around the maths enough, I should be able to use it in my answer – but I don't think I'd be able to get it this small. – wizzwizz4 Dec 13 '20 at 12:28

The easiest solution is to assume they're both below `modulus` already, then do `if (result >= modulus) result -= modulus;` – same as the method in the question, but with faster subtraction (or addition) instead of division.

Since `210` is between `128` and `256`, this is even easier. I don't know 6502, so here's some fake C:

``````const mod = 210;

char sum_mod(char a, char b) {
a = a + b;
if (!CARRY) goto later;
a -= mod;
if (!CARRY) goto again;
later:  COMPARE(a, mod);
if (!(a > mod)) goto after;
again:  a -= mod;
after:  return a;
}
``````

For modulus less than 128, you'd need to compare and subtract successively smaller `(mod << n)`, after the overflow check. The overflow check should use the largest `(mod << n)` (i.e., the largest less than `256`; including as the `again` target), because the important part is just to get it back under the overflow threshold so normal mathematics works again.

## Explanation

Theoretical `a + b` might be:

• `>= 0` and `< mod`: both of the conditional jumps encountered will be followed, and `a + b` will be returned.
• `> mod` but `< 256`: the carry flag is not set, so the `later` jump will be followed, but neither the `again` nor `after` jump will; this means that `a + b - mod` will be returned.
• `> 255` and `< 2 * mod`: the carry flag is set, so the `later` jump won't be followed, and then the `after` jump will; this means that `a + b - mod` will be returned.
• `>= 2 * mod` and `< mod + 256`: no jump will be followed, so `a + b - 2 * mod` will be returned.
• `> mod + 255` and `< 511`: `again` will be followed, so `a + b - 2 * mod` will be returned.

Thanks to Raffzahn for pointing out the need for the `again` jump. (And sorry for the useless label names.)

• This will fail if 'a+b' is larger than the char type used, whcihis quite likely with mod being already 201 (!). In fact, it needs to be an unsigned char at least, as mod is already larger than 128. – Raffzahn Dec 13 '20 at 1:04
• I think this approach would work. An overflow will be undone by subtracting mod in case of a set carry after the addition. If it is given that a and b were within the modulus, the sum can be at most one modulus above the result. For example a=\$AA + b=\$C8 would yield \$72 with carry set, after subtracting a modulo of \$d2 (210) we get the correct result of \$A0. But label `after` in above code is misplaced, needs to go down one line. – Peter B. Dec 13 '20 at 1:37
• @PeterB. These are quite some restrictions, and I can't read any of them in the original question. You reduce the task to adding (and cutting) two values that are guaranteed to be smaller than the modulus value - like in handling two digits of a modulus type numeric system, but there is no such requirement within the question. So input can ad well be 202+202 equals 2 remainder 2. – Raffzahn Dec 13 '20 at 2:36
• @Raffzahn thanks for bringing this up. If the two numbers can be anything within the datatype's range, the solution becomes more cumbersome. I asked for clarification if this can be the case and will edit my answer if necessary. – Peter B. Dec 13 '20 at 2:49
• @Raffzahn It won't necessarily, but I think you're right that it'll fail if it's much larger. I'll see if I can correct it. – wizzwizz4 Dec 13 '20 at 12:00

Given the assumption that 0 < A < modulus and 0 < B < modulus, than the following routine for 6502 (following the suggested algorithm of wizzwizz4) does the job:

``````MODULUS=201
varA=\$FC
varB=\$FD

;numbers A and B must be < MODULUS
;returns with the value (A+B) mod MODULUS in Accu

clc
lda varA
;we only need this if the added numbers could overflow
.if MODULUS>=128
bcc no_overflow
sbc #MODULUS
rts
.endif
no_overflow:
cmp #MODULUS
bcc exit
sbc #MODULUS ;carry is 1 because of past two lines
exit:
rts
``````

I tested several combinations of modulus, A and B with a BASIC program

``````10 FORM=5TO255STEP37
20 POKE49160,M:POKE49163,M:POKE49167,M
30 FORA=1TOM-1STEP1+INT(M/37)
40 FORB=4TOM-1STEP1+INT(M/26)
50 POKE252,A:POKE253,B:SYS49152
60 C=PEEK(780)
70 D=A+B:IFD>=MTHEND=D-M
80 IFC<>DTHEN PRINTM;A,B,C,D:END
90 NEXTB,A,M
``````

finding it working in all tested cases.

Shortened version hinted by David:

``````MODULUS=201
varA=\$FC
varB=\$FD

;numbers A and B must be < MODULUS
;returns with the value (A+B) mod MODULUS in Accu
clc
lda varA
;we only need this if the added numbers could overflow
.if MODULUS>=128
bcs overflow
.endif
cmp #MODULUS
bcc exit
overflow:
sbc #MODULUS ;carry is already set
exit:
rts
``````

Automatic testing program for second version:

``````10 FORM=5TO255STEP37
20 POKE49160,M:POKE49164,M
30 FORA=1TOM-1STEP1+INT(M/37)
40 FORB=4TOM-1STEP1+INT(M/26)
50 POKE252,A:POKE253,B:SYS49152
60 C=PEEK(780)
70 D=A+B:IFD>=MTHEND=D-M
80 IFC<>DTHEN PRINTM;A,B,C,D:END
90 NEXTB,A,M
``````

Some example testcases for manual testing:

``````A=0, B=0 -> (A+B)%201=0
A=1, B=1 -> (A+B)%201=2
A=100, B=100 -> (A+B)%201=200
A=101, B=100 -> (A+B)%201=0
A=200, B=0 -> (A+B)%201=200
A=200, B=1 -> (A+B)%201=0
A=200, B=200 -> (A+B)%201=199
``````
• you might want to read the question first. – Raffzahn Dec 13 '20 at 2:24
• With all the assumptions done here (especially a/b < mod-value), the solution can be reached with just 4 instructions: `LDA value_a; SEC; SBC #201; ADC value_b` carry now holds the result, so `LDA #0; ADC #0` will transfer it into A. No need for complicated comparison and conditioned assembly. Instead just using the way 8 bit unsigned works. Works for all values of modulus up to 255 (ofc with the restriction that a and b are smaller thant that - as with your solution) – Raffzahn Dec 13 '20 at 2:52
• This one's interesting to me because it acts after a normal addition, which may suit my code a bit better, and so be worth the extra comparison. It can also be simplified a bit --- flip the `bcc` to a `bcs` and jump to the trailing `sbc`. – David Given Dec 13 '20 at 22:53

If one needs to compute the mod-201 sum of many values, a useful technique is e.g.

``````    ; Compute the mod-M sum of N values, for N up to 129.
; Easily adaptable for 256 values, or for other numbers of values.
ldy #N-1
lda #256-M
clc
loop: