Division by a constant integer: Difference between revisions

From NESdev Wiki
Jump to navigationJump to search
(→‎Division by a constant: link to Omegamatrix's useful division code)
(Rewording, no more 2nd person)
Line 12: Line 12:
==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 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]]).


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 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.
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
Line 42: Line 42:
+    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 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.


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.


== Division of a constant by a variable ratio ==
== 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 ?
Is it possible to optimize the algorithm if the numerator is constant and the denominator variable ? To be written.
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.

Revision as of 19:33, 28 April 2017

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 doing a divison with a constant denominator, it is possible take advantage of this to optimise 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 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 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 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 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.