Morgan - Numerical Methods (523161), страница 14
Текст из файла (страница 14)
This is the normalization.5.Move the normalized dividend into DX:AX and divide by the normalizeddivisor.6.Point to the quotient with BX and the top of the workspace with DI.7.Multiply the divisor by the approximate quotient and subtract the resultfrom a copy of the original dividend.If there is no overflow, you have the correct quotient and remainder.Otherwise, decrement the approximate quotient by one and go back to thebeginning of step 7. This is necessary to get the correct remainder.8.74Write the remainder, clear the carry for success, and go home.INTEGERSdiv32: Listing; *****;div32;32-by-32-bit divide;Arguments are passed on the stack along with pointers to the;quotient and remainder.div32 proc uses ax dx di si,dvdnd:dword, dvsr:dword, qtnt:word, rmndr:wordlocalworkspace[8] :wordsubax, axmovdx, amovcx, 2leasi, word ptr dvdndleadi, word ptr workspacerepmovswmovcx, 2leasi, word ptr dvsrleadi, word ptr workspace[4]repmovswmovdi, word ptr qtntword ptr dvdnd, axcmPdo-dividejneword ptr dvdnd[2], axcmpjnedo_divide;check for azero_div;zero dividendjmpdo_divide:word ptr dvsr[2],axcmpjneshift;see if it is small enoughword ptr dvsr, ax;check for divide by zerocmpdiv_by_zero;as long as dx is zero,je;no overflow is possiblemovbx, word ptr rmndr;point at remaindermovax, word ptr dvdnd[2];first divide upper worddivword ptr dvsrword ptr [di][2],axmov;and save itmovax, word ptr dvdnddivword ptr dvsr;then the lower wordmovword ptr [di],ax;and save itmovword ptr [bx],dx;save remainderxorax,axmovword ptr [bx][2],axexitjmp75NUMERICAL METHODSshift:shrword ptr dvdnd[2], 1rcrshrrcrcmpwordwordwordwordjneshiftptrptrptrptrdvdnd[0], 1dvsr[2], 1dvsr[0], 1dvsr[2],ax;normalize both dvsr and;dvdnd;shift both the same number;shift until last one;leaves upper worddivide:movmovdivmovget-remaindermovleareconstruct:movmulmovmovmovmuladdmovmovsubax, worddx, wordword ptrword ptrptr dvdndptr dvdnd[2]dvsr[di] [0], axbx, didi, word ptr workspace[8]ax, word ptr workspace[4]word ptr [bx]word ptr [di] [0], axword ptr [di][2], dxax, word ptr workspace[6]word ptr [bx]word ptr [di][2], axax, word ptr workspace[0]dx, word ptr workspace[2]ax, word ptr [di] [0]sbbjncdx, word ptr [di][2]div_exmovmovsubsbbjmpax, word ptr [bx]dx, word ptr [bx][2]word ptr [bx], 1word ptr [bx] [2], 0short reconstructmovdi, word ptr rmndrmovmovword ptr [di], axword ptr [di] [2], dx;since MSB of dvsr is a one, no;overflow is possible here;approximate quotient;quotient;test first approximation of;quotient by multiplying it by;dvsr and comparing it with dvdnd;low word of multiplicand by;low word of multiplier;high word of multiplicand by;low word of multiplier;compare results of divide;approximation;good or overflows;overflow, decrement approx;quotient;decrement the quotientdiv_ex:76;the result is a good quotient;and remainderINTEGERSclcexit:retdiv_by_zero:notmovmovstcjmpzero_div:movmovstcjmpdiv32 endpaxword ptr [di][0], axord ptr [di] [2], ax;division by zeroexit;division of zeroword ptr [di][0], axword ptr [di][21, axexitIf very large operands are possible and the greatest possible precision andaccuracy is required, there is a very good method using a form of linear interpolation.This is very useful on machines of limited word length.
In this technique, the divisionis performed twice, each time by only the Most Significant Word of the divisor, oncerounded down and once rounded up to get the two limits between which the actualquotient exists. In order to better understand how this works, take the example,98765432H/54321111H. The word size of the example machine will be 16 bits,which means that the MSW of the divisor is 5432H * 216. The remaining divisor bitsshould be imagined to be a fractional extension of the divisor, in this manner:5432.1111H.The first division is of the form:987654328/54320000Hand produces the result:1.cf910000H.Next, increment the divisor, and perform the following division:77NUMERICAL METHODS98765432H/54330000Hfor the second quotient:1.cf8c0000H.Now, take the difference between these two values:1cf9l0000H - 1cf8c0000H = 50000H.This is the range within which the true quotient exists.
To find it, multiply thefraction part of the divisor described in the lines above by this range:50000H * .1111H = 5555H,and subtract this from the first quotient:1cf910000H - 5555H = 1.cf90aaabH.To prove this result is correct, convert this fixed point result to decimal, yielding:1.810801188229D.Convert the operands to decimal, as well:98765432H/54321111H = 2557891634D/1412567313D = 1.81081043746D.This divide does not produce a remainder in the same way the division above does;its result is true fixed point with a fractional part reflecting the remainder. Thismethod can be very useful for reducing the time it takes to perform otherwise timeconsuming multiple precision divisions.
However, for maximum efficiency, itrequires that the position of the Most Significant Word of the divisor and dividendbe known in advance. If they are not known, the routine is responsible for locatingthese bits, so that an attempt to divide zero, or divide by zero, does not occur.The next routine, div64, was specially written for the floating point divide in78INTEGERSChapter Four. This method was chosen, because it can provide distinct advantagesin code size and speed in those instances in which the position of the upper bits ofeach operand is known in advance.
In the next chapter, two routines are presentedthat perform highly accurate division without this need. They, however, have theirown complexities.To begin with, the operands are broken into word sizes (machine dependent),and an initial division on the entire dividend is performed using the MSW of thedivisor and saved.
The MSW of the divisor is incremented and the same division isperformed again, this will, of course result in a quotient smaller than the first division.The two quotients are then subtracted from one another, the second quotient from thefirst, with the result of this sutraction multiplied by the remaining bits of the divisoras a fractional multiply. This product is subtracted from the first quotient to yield ahighly accurate result. The final accuracy of this operation is not to the precision youdesire, it can be improved by introducing another different iteration.div64: Algorithm1.Clear the result and temporary variables.2.Divide the entire dividend by the Most Significant Word of the divisor.(The remaining bits will be considered the fractional part.)This is the first quotient, the larger of the two, save this result ina temporary variable.3.Increment the divisor.If there is an overflow, the next divide is really by 216, therefore,shift the dividend by 16 bits and save in a temporary variable.Continue with step 5.4.Divide the entire dividend by the incremented divisor.This is the second quotient, the smaller of the two, save this resultin a temporary variable.5.Subtract the second quotient from the first.6.Multiply the result of this subtraction by the fractional part of thedivisor.7.Subtract the integer portion of this result from the first quotient.8.Write the result of step 7 to the output and return.79NUMERICAL METHODSdiv64: Listing; ******;div64;will divide a quad word operand by a divisor;dividend occupies upper three words of a 6 word array;divisor occupies lower three words of a 6 word array;used by floating point division onlydiv64 proc uses es ds,dvdnd:qword, dvsr:qword, qtnt:wordlocalresult:tbyte, tmp0:qword,tmpl:qword, opa:qword, opb:qwordpushfcldreprepsubleamovstoswleamovstoswsetup:movcontinue_setup:lealeasubmovdiVmovmovdivmovsubmovdivmov80ax, axdi, word ptr resultcx, 4di, word ptr tmp0cx, 4;quotientbx, word ptr dvsr[3]si, word ptr dvdnddi, word ptr tmp0a, dxax, word ptr [si][3]bxword ptr [di][4], axax, word ptr [si][1]bxword ptr [di][2], axax, axah, byte ptr [si]bxword ptr[di] [O], ax;divisor no higher than;receives stuff for quotient;result goes into temporary varriable;entire first approximationINTEGERSlealeasubaddjncsi, word ptr dvdnddi, word ptr tmpldx, dxbx, 1as_beforemovax, word ptr [si] [3];divisor no higher than;receives stuff for quotient;round divisor up;if the increment results inoverflow;there is no divide, only a;shift by 216mov word ptr [di][2], axmov ax, word ptr [si] [l]movword ptr [di][0], axjmpfind-differenceas-before:movdivmovmovdivmovsubmovdivmovax, word ptr [si] [3]bxword ptr [di][4], axax, word ptr [si] [l]bxword ptr [di][2], axa, axah, byte ptr [si]bxword ptr [di] [0], axfind-difference:invokesub64, tmp0, tmp1, addr opareplealeamovmovsbsubstosbstoswsi, word ptr dvsrdi, word ptr opbcx, 3invokemu164a, opa, opb, addr resultleasi, word ptr result[3];divide entire dividend by new;divisor;result goes into quotient;result goes into quotient;result goes into quotient;get the difference between the;two extremesax, ax;fractional multiply to get;portion of;difference to subtract from;initial quotient81NUMERICAL METHODSrepleamovmovsbsubstosbstoswdi, word ptr opbcx, 3invokeleasub64,tmp0, opb, addr tmp0si, word ptr tmp0;(high quotient)ax, ax;subtract and write out resultdiv_exit:movdi, word ptr qtntmov cx, 4rep movswpopfretdiv64 endpWhen writing arithmetic routines, keep the following in mind:Addition can always result in the number of bits in the largest summend plusone.Subtraction requires at least the number of bits in the largest operand for theresult and possibly a sign.The number of bits in the product of a multiplication is always equal to log,multiplier + log, multiplicand.
It is safest to allow 2n bits for an n-bit by nbit multiplication.The size, in bits, of the quotient of a division is equal to the difference, log,dividend - log2, divisor. Allow as many bits in the quotient as in the dividend.82INTEGERS12Microsoft Macro Assembler Reference. Version 6.0. Redmond, WA: MicrosoftCorp., 1991.Cavanagh, Joseph J. F. Digital Computer Arithmetic. New York, NY: McGrawHill Book Co., 1984, Page 148.8384Previous HomeCHAPTER 3Real NumbersThere are two kinds of fractions. A symbolic fraction represents a divisionoperation, the numerator being the dividend and the denominator the divisor.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
