Division by a constant integer: Difference between revisions

From NESdev Wiki
Jump to navigationJump to search
m (→‎Divide by a power of two: No mode 2nd person wording)
(Fixes)
Line 1: Line 1:
==Divide by a power of two==
==Divide by a power of two==
In binary arithmetic, division by 2^n is equivalent to shifting right n times. For this reason, it is recommended that each NES project is designed 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.
In binary arithmetic, division by 2^n is equivalent to shifting right n times. For this reason, it is recommended that each NES project is designed in a way that takes advantage of this fact. The rest of the division by 2^n can be easily obtained 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 :
For signed numbers, it is required that the bit shifting "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 arithmetic shift right instruction, it can be achieved that way :
<pre>
<pre>
     cmp #$80
     cmp #$80
Line 11: Line 11:
==Division by a constant==
==Division by a constant==


When doing a divison with a constant denominator, it is possible take advantage of this to optimise code (as opposed to use the general purpose [[8-bit Divide|division by 2 variables]]).
When doing a division with a constant denominator, it is possible take advantage of this to optimize code (as opposed to use the general purpose [[8-bit Divide|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).
First thing is to decompose the constant number into sum-of-power-of-two (i.e. write it in binary form).
It then needs to be determined how many bits are needed to hold the result. Let's call the number of bits n, and let's call the constant divisor c.
It then needs to be determined how many bits are needed to hold the result. Let's call the number of bits n, and let's call the constant divisor c.
For each bit k, compare the variable it to c<<k (= c*2^k) (in the order k = n-1, n-2, ... downto 0 included).
For each bit k, compare the variable 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).
If the comparison bit is set, subtract c<<k, and in all cases rotate the result left (note that after the subtraction c will always be set).
For example this division code divides the variable in A by 14 and keeps the lower 4 bit of results.
For example this division code divides the variable in A by 14 and keeps the lower 4 bit of results.
<pre>
<pre>
Line 22: Line 22:
       pha
       pha
       lda #$00
       lda #$00
       sta Res      ;Init the res varialbe (needed because we're doing less than 8 shifts)
       sta Res      ;Init the res variable (needed because we're doing less than 8 shifts)
       pla
       pla
       cmp #$70    ;Compare to 14<<3 and set bit
       cmp #$70    ;Compare to 14<<3 and set bit
Line 41: Line 41:
+    rol Res      ;A = remainder, Res = quotient
+    rol Res      ;A = remainder, Res = quotient
</pre>
</pre>
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 a larger number of bits is expected, the code should be adapted to take that into account.
Of course the result will only be correct if if fits in 4-bit in the above example (because it does 4 compare/shift operations), if a larger number of bits is expected, the code should be adapted to take that into account.


See also: [http://forums.nesdev.org/viewtopic.php?f=2&t=11336 Unsigned Integer Division Routines] - NESDev forum post with a collection of efficient 8-bit division by constant routines.
See also: [http://forums.nesdev.org/viewtopic.php?f=2&t=11336 Unsigned Integer Division Routines] - NESDev forum post with a collection of efficient 8-bit division by constant routines.

Revision as of 16:06, 29 April 2017

Divide by a power of two

In binary arithmetic, division by 2^n is equivalent to shifting right n times. For this reason, it is recommended that each NES project is designed in a way that takes advantage of this fact. The rest of the division by 2^n can be easily obtained by ANDing the original value by (2^n)-1.

For signed numbers, it is required that the bit shifting "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 arithmetic shift right instruction, it can be achieved 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 doing a division with a constant denominator, 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). It then needs to be determined how many bits are needed to hold the result. Let's call the number of bits n, and let's call the constant divisor c. For each bit k, compare the variable it to c<<k (= c*2^k) (in the order k = n-1, n-2, ... downto 0 included). If the comparison bit is set, subtract c<<k, and in all cases rotate the result left (note that after the subtraction c will always be set). For example this division code divides 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 variable (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 course the result will only be correct if if fits in 4-bit in the above example (because it does 4 compare/shift operations), if a larger number of bits is expected, the code should be adapted 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

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 an algorithm 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.