Math Method

Binary Division by a Constant

Division by some constants are very easy in binary math. Good bets are:

• Any multiple of 2 (obviously)
• 1000 (since it is close to 1024) and is nice for binary to decimal conversions.
• 60 (close to 64) and is nice for working with degrees and minutes or seconds.

Robert A. LaBudde, PhD, PAS, Dpl. ACAFS

If you only need to divide by five, and you don't want to write a standard division routine, you can do the following:

X / 5 = X/(4+1) = (X/4) /(1+1/4)= (X/4) * (1 - 1/4 + 1/16 - 1/64 + 1/256 ...)
      = X/4 - X/16 + X/64 - X/256 + X/1024 - X/4096 ...

1. Form y = x/4. (You shift your dividend by 2 bits to the right.)
2. Add y to sum.
2. Form z = y/4. Subtract from sum.
3. Form w = z/4. Add to sum.
4. Form v = w/4. Subtract from sum. (This is sufficient for 3DE or less.)
5. Form u = v/4. Add to sum.
6. Form t = u/4. Add to sum.
7. Form s = u/4. Add to sum. (This is sufficient for FFFF dividend.)

Nikolai Golovchenko says

If you have to divide or multiply a number by a constant there is a possibility to optimize this routine for the given constant. Multiplication and division are treated the same, because the constant can be fractional and regarded as multiplier in both cases.

Example:
Assume constant multiplier c=3.578 and variable v is 16 bit long.

Step1. Convert c to binary fractional form:

3.578(dec) = 11.1001 0011 1111 0111 1100 ...(bin)

Step2. Replace series of ones with difference
All series of two and more one's can be replaced by differences. For example, 1111 = 10000 - 1. The difference requires only one substraction instead of four additions.

If there are no such series than optimization not possible.

3.578(dec) = 100.0001 0100 0000 0000 0000..(bin)
             - 0.1000 0000 0000 0000 0100..(bin)
           = 4 - 1/2 + 1/16 + 1/64 - ...(dec).

Step3. Limit fractional part of positive and negative constant multiplier to 16-1 bits. 16th bit can be used to round multiplication result.

3.578 = 4 - 1/2 + 1/16 + 1/64

Step4.Now shift v and add and sub...... ;)

on Signed divide:

   rlf reg, w    ;sign extension
   rrf reg, f

How about fixing it by adding 1 to the dividend before shifts if the
dividend is negative:

-1/2 = 0
(-1+1) >> 1 = 0

-2/2 = -1
(-2+1) >>1 = -1

-3/2 = -1
(-3+1) >> 1 = -1

James Newton has written a small QBASIC program to generate the sequence of operations required for a given Divisor and # of bits of precision. Updated with help from Nicholai:

INPUT "enter number to divide by: ", in
INPUT "bits precision: ", bits

accum = -1 / in
i = 1
j = 1
WHILE j < bits
    ni = i / 2
    IF accum < 0 THEN 'neg
        IF ABS(accum + ni) > ABS(accum + i) THEN
           PRINT "Add dividend to accumulator (dividend /"; 1 / i ;")"
           accum = accum + i
           END IF
    ELSE
        IF ABS(accum - ni) > ABS(accum - i) THEN
           PRINT "Subtract dividend from accumulator (dividend /"; 1 / i ;")"
           accum = accum - i
           END IF
        END IF
    PRINT "Shift dividend right. Shift#"; j
    j = j + 1
    i = ni
    WEND
IF  accum <> 0 THEN
    PRINT "Final error:"; accum; "would require 1/"; 1 / accum; "th of dividend to be added to accumulator"
ELSE
    PRINT "no error"
    ENDIF

Nikolai and James are working on a code generator for the PIC Microcontroller using this basic method with (really nice) optimizations by Nikolai: See:
http://www.piclist.com/codegen
http://www.piclist.com/codegen/constdivmul

David Parker says:

The closest trick that I have seen for constants that are not powers of two is to multiply by 2^32/(integer constant), making sure that 2^32/(integer constant) is rounded towards infinity. For example [on the x86 32bit], to divide Edx by 10, you could use the following:

; Edx = unsigned integer.
  Mov   Eax,(1 Shl 31)/5+1 ; 2^32/10 = 2^31/5, plus 1 for rounding.
  Mul   Edx ; Multiply Edx by 1/10.
; Edx = Edx/10, rounded toward 0, Eax = destroyed.

On many machines the Mul instruction isn't all that speedy, so this trick is of limited usefulness. On the other hand, if you are using floating point numbers then multiplying by 1/constant is usually much more efficient than dividing by the constant.

See also:

• http://www.davidparker.com/assembly.html#tips-and-tricks-divide-by-a-constant (cached 20000210)
• http://www.azillionmonkeys.com/qed/adiv.html x86 Integer division and modulus by constants. by Paul Hsieh
• http://www.cs.uiowa.edu/~jones/bcd/divide.html An excellent tutorial on Reciprocal Multiplication especially by 10 (1/10)

Comments:

• jonw0224 at netscape.net

  As another approach to this problem, you can do a "full divide" but take advantage of the fact that you know certain things about the number with which you are dividing. Just as an example, here is a MACRO I use for dividing an eight bit number by a constant {on the PIC microcontroller}:

  ;DIVIDEL divides WREG by a literal value.  It gives the quotient in reg and ;the remainder in WREG.
  ;reg:  the register to place the quotient
  ;lit:  the literal with which WREG is divided
  ;------------------------------------------------------------------------------
  DIVIDEL macro reg, lit
      clrf reg                    ;Set at zero to begin
      local divi, cnt
      divi = lit
      cnt = 0
      while (divi & 0x80) == 0    ;Shift literal until MSB is in bit 7
          divi <<= 1
          cnt++                   ;Keep up with number of shifts
      endw
      while cnt >= 0
          addlw 0 - divi          ;Subtract shifted literal
          btfsc STATUS, C         ;If positive then
              bsf reg, cnt        ;   set appropriate bit (i.e. divides once)
          btfss STATUS, C         ;else
              addlw divi          ;   add back to restore number
          divi >>= 1              ;shift literal and continue until done
          cnt--
      endw
      endm
  
  

  It doesn't approximate the divide with a shifted multiply and it also has the side effect of placing the remainder in WREG. It does, however, generate more instructions and take a little more time. Divide by 3 takes 35 cycles (and instruction words) instead of 17 cycles.
   

• I just worked through Robert Labudde's algorithm and found it doesn't work unless a fractional divide is used. In other words, the divisions won't work when using integer math. Although this routine may be useful on a PIC very specific conditions, I would have thought in general it would be more useful to have something that would work for integers.

  I use this one for dividing by 10.

  For Y = X/10:
  Y = (X + X/2 + X/8 - X/64) / 16
  

  This will work with 8 bit registers only, for numbers up to 159 without underflow or overflow or any of those bad things.

  The X/64 term can be dropped, giving a operating range of up to 88, which is handy for converting seconds and minutes (which only go up to 59).

  Ashley Preston
  ashley@ieee.org +

Questions:

• derek at proconsys.freeserve.co.uk asks:

  I have a Microchip PIC16F627, and need to add 3, 8 bit analogue numbers together, then divide by 3. The divide is giving me a headache!. I've tryed all the MATH divide links and they all fail. I'm using the assembler instruction set in MPLAB. Can anyone email me a short, simple piece of code that works ?

  James Newton replies: http://www.piclist.com/cgi-bin/constdivmul.exe?Acc=ACC&Bits=8&endian=little&Const=.333333&ConstErr=0.5&Temp=TEMP&cpu=pic16 Seems to work for me...+

  +

Code:

• https://web.archive.org/web/20190915025154/http://www.hackersdelight.org/

  unsigned divu10(unsigned n) {
    unsigned q, r;
    q = (n >> 1) + (n >> 2); // q=n/2+n/4 = 3n/4
    q = q + (q >> 4);        // q=3n/4+(3n/4)/16 = 3n/4+3n/64 = 51n/644
    q = q + (q >> 8);        // q=51n/64+(51n/64)/256 = 51n/64 + 51n/16384 = 13107n/16384 q = q + (q >> 16); 
    // q= 13107n/16384+(13107n/16384)/65536=13107n/16348+13107n/1073741824=858993458n/1073741824
    // note: q is now roughly 0.8n
    q = q >> 3;              // q=n/8 = (about 0.1n or n/10)
    r = n - (((q << 2) + q) << 1); // rounding: r= n-2*(n/10*4+n/10)=n-2*5n/10=n-10n/10
    return q + (r > 9);      // adjust answer by error term
  }

  +

  .