Notes on Binary Division by a Constant

NOTES ON BINARY DIVISION BY A CONSTANT:

Division by some constants are very easy in binary math:

QUOTE

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

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

CODE

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:

QUOTE

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.

Step 1. Convert c to binary fractional form:

CODE

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:

CODE

1111 = 10000 - 1.

The difference requires only one substraction instead of four additions.

If there are no such series than optimization not possible.

CODE

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.

CODE

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

Step4.Now shift v and add and sub...... ;)
on Signed divide:

CODE

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:

CODE

-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:

CODE

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:

QUOTE

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:

CODE

; 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#t...e-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)

jonw0224@netscape.net comments:

QUOTE

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}:

CODE

;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.

CODE

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