Morgan - Numerical Methods (523161), страница 13
Текст из файла (страница 13)
The integers these routines are meant to handle are unsigned; the method forsigned division is the same as for multiplication which was described earlier (seeSigned vs. Unsigned), and is demonstrated in FXMATH.ASM.cdiv: Algorithm1.Load the quotient (qtnt) with the dividend (dvdnd); set an onboardregister, si, with the number of bits in the dividend(this will alsobe the size of our quotient); and clear registers AX, BX, CX, and DX.2.Left-shift the dividend into the quotient and remainder simultaneously.3.Compare rmdr and dvsr.If dvsr > = rmndr, subtract dvsr from rmndr and increment qtnt.Otherwise, fall through to the next step.4.Decrement si and test it for zero.
If si is not 0, return to step 2.5.Write the remainder and leave.This will work for any size data type and, as you can see, is basically an iterativesubtract.67NUMERICAL METHODScdiv: Listing;*****; classic divide; one quadword by another, passed on the stack, pointers returned; to the results; composed of shift and sub instructions; returns all zeros in remainder and quotient if attempt is made to divide; zero. Returns all ffs in quotient and dividend in remainder if divide by; zero is attempted.cdiv proc uses bx cx dx si di, dvdnd:qword, dvsr:qword,qtnt:word, rmndr:wordreppushfcldmovleamovmovswsubmovsubmovmovmov;upwardcx, 4si, word ptr dvdnddi, word ptr qtntdi,si,ax,bx,cx,dx,864axaxaxax;move dividend to quotient;dvdnd and qtnt share same;memory space;reset pointer;nurrber of bitsshift:shlrclrclrclrclrclrclrclcompare:cmpjbcmpjbcmpjbcmpjb68word ptr [dil, 1word ptr [dil[2],word ptr [dil[41,word ptr [di] [6],ax, 1bx, 1cx, 1dx, 1;shift quotient/dividend left;into registers (remainder)dx, word ptr dvsr[6];Compare the remainder and;divisortest-for-endcx, word ptr dvsr[4]test-for-endbx, word ptr dvsr[2]test-for-endax, word ptr dvsr[0]test-for-end;if remainder divisorINTEGERSsubsbbsbbsbbaddadcadcadctest_for_end:decjnzmovmovmovmovmovexit:popfretcdiv endpax, word ptr dvsrbx, wordcx, worddx, wordword ptrword ptrword ptrword ptrsishiftdi, wordword ptrword ptrword ptrword ptrptr dvsr[2]ptr dvsr[4]ptr dvsr[6][di], 1[di][2], 0[di][4], 0[di][6], 0;if it is greater than;the divisor;subtract the divisor and;increment the quotient;decrement the counterptr rmndr[di], ax[di][2], bx[di][4], cx[di][6], dx;write remainder;to take care of cldHardware DivisionMany microprocessors and microcontrollers offer hardware divide instructionsthat execute within a few microseconds and produce accurate quotients and remainders.
Except in special cases, from the 80286 on up, the divide instructions have anadvantage over the shift-and-subtract methods in both code size (degree of complexity) and speed. Techniques that involve inversion and continued multiplication(examples of both are shown in Chapter 3) don’t stand a chance when it comes to theshorter divides these machine instructions were designed to handle.The 8086 offers hardware division for both signed and unsigned types; the 286,386, and 486 offer larger data types but with the same constraints. The DIVinstruction is an unsigned divide, in which an implied destination operand is dividedby a specific source operand. If the divisor is 16 bits wide, the dividend is assumedto be in DX:AX. The results of the division are returned in the same register pair (thequotient goes in AX and the remainder in DX).
If the divisor is only eight bits wide,the dividend is expected to be in AX; at the end of the operation, AL will contain thequotient, while AH will hold the remainder.69NUMERICAL METHODSAs a result, you should make sure the implied operands are set correctly.
Forexample,divcxsays that DX:AX is to be divided by the 16-bit quantity in CX. It also means that DXwill then be replaced by the remainder and AX by the quotient. This is importantbecause not all divisions turn out neatly. Suppose you need to divide a 16-bit quantityby a 9-bit quantity. You’ll probably want to use the 16-bit form presented in theexample. Since your dividend is only a word wide, it will fit neatly in AX. Unless youzero DX, you’ll get erroneous results.
This instruction divides the entire DX:AXregister pair by the 16-bit value in CX. This can be a major annoyance and somethingyou need to be aware of.As nice as it is to have these instructions available, they do have a limitation;what if you want to perform a divide using operands larger than their largest datatype? The 8086 will allow only a 32-bit dividend and a 16-bit divisor. With the 386and 486, the size of the dividends has grown to 64 bits with divisors of 32;nevertheless, if you intend to do double-precision floating point, these formats arestill too small for a single divide.Several techniques are available for working around these problems. Actually,the hardware divide instructions can be made to work quite well on very largenumbers and with divisors that don’t fit so neatly in a package.Division of very large numbers can be handled in much the same fashion ashardware multiplication was on similarly large numbers.
Begin by dividing the mostsignificant digits, using the remainders from these divisions as the upper words (orbytes) in the division of the next most significant digits. Store each subquotient asa less and less significant digit in the main quotient.The number 987654321022H can be divided by a 2987H bit on the 8086 usingthe 16-bit divide, as follows (also see Figure 2-2):1. Allocate storage for intermediate results and for the final quotient. Assuming 32 bits for the quotient (qtnt) and 16 bits for the remainder (rmndr), threewords will be required for the dividend (dvdnd) and only 16 bits for the divisor70INTEGERSFigure 2-2. Multiprecision division(dvsr).
Actually, the number of bits in the QUOTIENT is equal to thelog, DIVIDEND - log2, DIVISOR, or 34 bits.2.Clear DX, load the most significant word of the dividend into AX and thedivisor into CX, and divide:sub,movdivdx, dxax, word ptr dvdnd[4]cx;9876;divide3 . At the completion of the operation, AX will hold 3 and DX will hold 1 be 1H.4.Store AX in the upper word of the quotient:mov5.word ptr qtnt[4], ax;3HWith the remainder still in DX as the upper word of the “new” dividend, load71NUMERICAL METHODSthe next most significant word into AX and divide again:movdiv6.word ptr qtnt[2],ax;OabdeHDivide DX:AX one final time:movdiv8.;5432H;recall that the divisor;is still in CXNow DX holds 2420H and AX holds 0abdeH as the remainder. Store AX inthe next most significant word of the quotient and put the least significant wordof the dividend into AX.mov7.ax, word ptr dvdnd[2]cxax, word ptr dvdnd[0]cxStore the result AX in the least significant word of the quotient and DXin the remainder.movmovword ptr qtnt[0],axword ptr rmndr,dx;0deb2H;le44HThis technique can be used on arbitrarily large numbers; it’s simply a matter ofhaving enough storage available.What if both the divisor and the dividend are too large for the hardware to handleby itself? There are at least two ways to handle this.
In the case below, the operandsare of nearly equal size and only need to be normalized; that is, each must be dividedor right-shifted by an amount great enough to bring the divisor into range for ahardware divide (on an 8086, this would be a word). This normalization doesn’taffect the integer result, since both operands experience the same number of shifts.Because the divisor is truncated, however, there is a limitation to the accuracy andprecision of this method.If we have good operands, right-shift the divisor, counting each shift, until it fits72INTEGERSwithin the largest data type allowed by the hardware instruction with the MSB a one.Right shift the dividend an equal number of shifts. Once this has been done, dividethe resulting values. This approximate quotient is then multiplied by the originaldivisor and subtracted from the original dividend.
If there is an underflow, thequotient is decremented, the new quotient multiplied by the divisor with that resultsubtracted from the original dividend to provide the remainder. When there is nounderflow, you have the correct quotient and remainder.Figure 2-3. Multiword division. This process can continue as long as there is a remainder.73NUMERICAL METHODSThe normalization mentioned earlier is illustrated in Figure 2-3. It requires onlythat the operands be shifted right until the 16 MSBs of the divisor reside within a wordand the MSB of that word is a one.An example of this technique for 32 bit operands is shown in div32.div32: Algorithm1.Set aside a workspace of eight words.
Load the dividend (dvdnd) into thelowest two words and the divisor (dvsr) into the next two words. Use DIto point to the quotient.2.Check to see that the dividend is not zero.If it is, clear the quotient, set the carry, and leave.3.Check for divide by zero.If division by zero has occurred, return -1 with the carry set.If the divisor is greater than a word, go to step 4.Use BX to point at the remainder (rmndr).Bring the most significant word of the dividend into AX (DX is zero) anddivide by the normalized divisor.Store the result in the upper word of the quotient.Bring the least significant word of the dividend into AX (DX containsthe remainder from the last division) and divide again.Store the result in the least significant word of the quotient.Store DX and clear the upper word of the remainder.4.Shift both the dividend and the divisor until the upper word of thedivisor is zero.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
