please dont rip this site

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:


file: /Techref/method/math/divconst.htm, 9KB, , updated: 2010/4/12 10:52, local time: 2014/9/30 06:49,
TOP NEW HELP FIND: 
23.20.77.156:LOG IN

 ©2014 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! / 

<A HREF="http://techref.massmind.org/techref/method/math/divconst.htm"> Binary Division by a Constant</A>

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


Link? Put it here: 
if you want a response, please enter your email address: 
Attn spammers: All posts are reviewed before being made visible to anyone other than the poster.
Did you find what you needed?

 

Welcome to massmind.org!

 

Welcome to techref.massmind.org!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  .