Division by a constant integer: Difference between revisions

From NESdev Wiki
Jump to navigationJump to search
(Created article)
 
(Add to arithmetic category)
(6 intermediate revisions by 4 users not shown)
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 (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.
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.
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 :
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 12: Line 11:
==Division by a constant==
==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 [[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).
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.
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.
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).
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 divide 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>
;Division by 14
;Division by 14
       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 42: 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 you except a larger number of bits you should adapt your code 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.


== Division of a constant by a variable ratio ==
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.
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 ==
== 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.
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.
 
== Resources ==
 
* [https://forums.nesdev.org/viewtopic.php?t=11336 Unsigned Integer Division Routines] forum post by Omegamatrix with routines for many constants.
 
[[Category:Arithmetic]]

Revision as of 02:42, 26 February 2022

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.

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.

Resources