10

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?

6
  • 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
  • 1
    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
  • 1
    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
  • 1
    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. 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
11

Here's a shorter solution than wizzwizz4's:

  SEC
  LDA x
  SBC modulus
  ADC y
  BCS end
  ADC modulus
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.

2
  • 1
    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! 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
8

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

5
  • 3
    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
  • 1
    @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
2

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

;add two numbers A and B given in memory address
;numbers A and B must be < MODULUS
;returns with the value (A+B) mod MODULUS in Accu

        clc
        lda varA
        adc varB
        ;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

;add two numbers A and B given in memory address
;numbers A and B must be < MODULUS
;returns with the value (A+B) mod MODULUS in Accu
        clc
        lda varA
        adc varB
        ;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
3
  • 1
    you might want to read the question first.
    – Raffzahn
    Dec 13 '20 at 2:24
  • 1
    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
  • 1
    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. Dec 13 '20 at 22:53
1

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:
    adc values,y
    bcc noWrap
wrapped:
    sbc #M      ; Note that carry is set here
    bcs wrapped ; Could be omitted if original values are all less than M
noWrap:
    dey
    bpl loop
    adc #M ; Note carry is clear here

While performing the computation, there's no need for code to care about the modulus except when a carry occurs. At the end of the loop, the value in the accumulator will be equal to the correct residue plus (256-M), so adding M will negate the -M term.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.