Division by a constant integer

Divide by a power of two

In binary arithmetic, division by 2^n is equivalent to shifting right n times (technically this is true even if n is negative). For this reason, it is recommended that you design your NES project in a way that takes advantage of this fact. The rest of the division by 2^n can be easily obtainged by ANDing the original value by (2^n)-1.

For signed numbers, it is required that the bit shiting "in" the number at the left is the previous sign bit and not a '0'. This is commonly called an "arithmetic shift right" as opposed to a "logical shift right". Since the 6502 doesn't have any logical shift right instruction, it can be achevied that way :

    cmp #$80
    ror A

This will be true for all divisions discussed in this article, which focuses on unsigned numbers.

Division by a constant

When you want to divide 2 numbers, if the denominator is constant, it is possible take advantage of this to optimize code (as opposed to use the general purpose division by 2 variables).

First thing is to decompose the constant number into sum-of-power-of-two (i.e. write it in binary form). Then you'll need to know how many bits of the result you need, let's call this number n and let's call c your constant divisor. Take the variable number, and for each bit k, compare it to c<<k (= c*2^k) (in the order k = n-1, n-2, ... downto 0 included). If the comparaison bit is set, substract c<<k, and in all cases rotate the result left (note that after the substraction c will always be set). For example this division code divide the variable in A by 14 and keeps the lower 4 bit of results.

;Division by 14
      pha
      lda #$00
      sta Res      ;Init the res varialbe (needed because we're doing less than 8 shifts)
      pla
      cmp #$70     ;Compare to 14<<3 and set bit
      bcc + 
      sbc #$70 
+     rol Res 
      cmp #$38     ;14<<2
      bcc + 
      sbc #$38 
+     rol Res 
      cmp #$1c     ;14<<1
      bcc + 
      sbc #$1c 
+     rol Res 
      cmp #$0e     ;14<<0
      bcc + 
      sbc #$0e 
+     rol Res      ;A = remainder, Res = quotient

Of couse the result will only be correct if if fits in 4-bit in the above example (because it does 4 compare/shift operations), if you except a larger number of bits you should adapt your code to take that into account.

See also: Unsigned Integer Division Routines - NESDev forum post with a collection of efficient 8-bit division by constant routines.

Division of a constant by a variable ratio

When you divide 2 numbers, is it possible to optimize the algorithm if the numerator is constant and the denominator variable ? To be written.

Chain multiply by a variable

If you want to do an algorithm that does a really great number of divisions by a variable, but that the value of the variable is constant for the whole algorithm, it could be faster to write a code that generate the above code in RAM and execute it that way instead of doing the slower variable / variable code.