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/64Step4.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:
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 endmIt 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 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:
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:
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: 2023/3/22 14:51, |
©2023 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? <A HREF="http://massmind.org/Techref/method/math/divconst.htm"> Binary Division by a Constant</A> |
Did you find what you needed? |
Welcome to massmind.org! |
Welcome to massmind.org! |
.