Math Method

Binary Division by a Constant

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

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:

Comments:

Questions:

Code:

Interested: