# MathMethod

## 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.
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. 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.)
```
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.

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

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
}```
+

 file: /Techref/method/math/divconst.htm, 10KB, , updated: 2020/6/28 21:41, local time: 2022/5/23 08:08, TOP NEW HELP FIND:  3.238.72.122:LOG IN

 ©2022 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions?Please DO link to this page! Digg it! / MAKE! Binary Division by a Constant

After you find an appropriate page, you are invited to your to this massmind site! (posts will be visible only to you before review) Just type a nice message (short messages are blocked as spam) in the box and press the Post button. (HTML welcomed, but not the <A tag: Instead, use the link box to link to another page. A tutorial is available Members can login to post directly, become page editors, and be credited for their posts.

Attn spammers: All posts are reviewed before being made visible to anyone other than the poster.
 Did you find what you needed? "No. I'm looking for: " "No. Take me to the search page." "No. Take me to the top so I can drill down by catagory" "No. I'm willing to pay for help, please refer me to a qualified consultant" "No. But I'm interested. me at when this page is expanded."

### Welcome to sxlist.com!

Site supported by
& kind contributors
just like you!

(here's why

Copies of the site on CD
are available at minimal cost.

.