Morgan - Numerical Methods (523161), страница 19
Текст из файла (страница 19)
If a factor could be found, such that multiplying it by thedenominator causes the denominator to approach one, then multiplying the numerator by the same factor must cause that numerator to approach the quotient of the ratioor simply the result of the division.In this procedure, as in the last, you normalize the divisor, or numerator-thatis, shift it so that its most significant one is to the immediate right of the radix point,creating a number-such that .5 number < 1. To keep the ratio between thedenominator and numerator equal to the original fraction, perform the same numberof shifts, in the same direction, on the dividend or numerator.Next, express the divisor, which is equal to or greater than one half and less thanone, as one minus some offset:114REAL NUMBERSdivisor = l- offsetTo bring this number, 1- offset, closer to one, choose another number by whichto multiply it which will retain its original value and increase it by the offset, suchas:multiplier = 1 + offset.To derive the first attempt, multiply this multiplier by the divisor:multiplier * divisor = (1 - offset) * (1 + offset) = 1 - offset2followed by(1 + offset) * dividendAs you can see, the result of this single multiplication has brought the divisorcloser to one (and the dividend closer to the quotient).
For the next iteration, 1 - offset2is multiplied by 1 + offset2 (with a similar multiplication to the dividend). The resultis 1 - offset4, which is closer still to one. Each following iteration of 1 - offsetn ismultiplied by 1 + offsetn (with that same 1 + offsetn multiplying the dividend) untilthe divisor is one, or almost one, which is .11111111...B to the word size of themachine you’re working on. Since the same operation was performed on both thedividend and the divisor, the ratio did not change and you need not realign thequotient.To illustrate, let’s look at how this procedure works on the decimal division12345/1222.
Remember that a bit is a digit in binary. Normalizing the denominatorin the discussion above required shifting it so that its most significant one was to theimmediate right of the radix point. The same thing must be done to the denominatorin the decimal fraction 12345/1222D; 1222D becomes .9776D, and performing thesame number of shifts (in the same direction) on the numerator, 12345, yields9.8760D. Since the divisor (.9976D) is equal to 1 - .0224, make the first multiplier115NUMERICAL METHODSequal to 1 + .0224 and multiply divisor * (1.
+ .0224) = .99949824D. You then take9.8760D, the dividend, times (1. + .0224) to get 10.0972224D. On the next iteration,the multiplier is (1 + .02242), or l.000501760D, which multiplied by the denominator is .999999748D and by the numerator is 10.10228878D. Finally, multiplying.999999748D by (1 + .02244) produces a denominator of .999999999D, and (1 +.02244) times 10.10228878D equals 10.10229133D, our quotient.
The next routineillustrates one implementation of this idea.clivmul: Algorithm1. Set pass counter, lp, for 6, enough for a 64-bit result. Check bothoperands for zero,If either is zero, go to step 10.Otherwise continue with step 2.2.Find the most significant word of divisor, and see whether it is aboveor below the radix point,If it's below, normalization is to the left; go to step 3a.If it's above, normalization is to the right; go to step 3b.If it's right there, see whether it's already normalized.if so, skip to step 4.Otherwise, continue with step 3a.3.a) Shift a copy of the most significant word of the divisor left untilthe MSB is one, counting the shifts as you go.
Continue with step 4.b) Shift a copy of the most significant word of the divisor right untilit is zero, counting the shifts as you go. Continue with step 4.4.Shift the actual divisor so that the MSB of the most significant wordis one.5.Shift the dividend right or left the same number of bits as calculatedin step 3. This keeps the ratio between the dividend and the divisor thesame.6. Offset = 1 - normalized divisor.7.Multiply the offset by the divisor, saving the result in a temporaryregister.
Add the divisor to the temporary register to simulate themultiplication of 1 + offset by the divisor. Write the temporaryregister to the divisor.8.Multiply the offset by the dividend, saving the result in a temporary116REAL NUMBERSsimulate the multiplication of 1 + offset by the dividend.
Write thetemporary register to the divisor.9.Decrement 1p,If it's not yet zero, go to step 6.Otherwise, the current dividend is the quotient; exit.10. Overflow exit, leave with an error condition.divmul: Listing; *****;divmul-division by iterative multiplication;Underflow and overflow are determined by shifting. If the dividend shifts out on;any attempt to normalize, then we have "flowed" in whichever direction it;shifted out.;divmul proc uses bx cx dx di si, dividend:qword, divisor:qword, guotient:wordlocaldivmsb:byte,temp[8]:word, dvdnd:qword, dvsr:qword, delta:qword,lp:byte, tmp:qwordcld;upwardsubmovleamovmovorormovmovmovmovmovmovororjecx, cxbyte ptrdi, wordax, worddx, wordcx, axcx, dxword ptrword ptrax, worddx, wordword ptrword ptrcx, axcx, dxovrflwsubleamovmovcx,di,ax,dx,lp,ptrptrptr6dvdnddividend[O]dividend[2];should only take six passes;check for zero[di][0], ax[di][2], dxptr dividend[4]ptr dividend[6][di][4], ax[di][6], dxcxword ptr dvsrword ptr divisor[0]word ptr divisor[2];zero dividend;check for zero117NUMERICAL METHODSorormovmovmovmovmovmovororjesubmovfind_MSB:decdeccmpjecx, axcx, dxword ptrword ptrax, worddx, wordword ptrword ptrcx, axcx, dxovrflw[dil[0], ax[di] [2], dxptr divisor[4]ptr divisor[6][di][4], ax[di][6], dxax, axbx, 8;look for MSB of divisorbxbxword ptr [di] [bx], axfind msbmovsubcmpax, word ptr [di] [bx]cx, cxbx, 2hjbjatestjneshift leftshift rightword ptr [di][bxl, 8000hnorm dvsrshift_left:decshltestjnejmpcxax, 1ah, 80hnorm_dvsrshift_leftshift_right:incshrorjejmpcxax, 1ax, axnorm_dvsrshift_right118;zero divisor;di is pointing at dvsr;get MSW;save shifts here;see if already;normalized;normalized?;it's already there;count the number of;shifts to normalize;count the number of shifts;to normalizeREAL NUMBERSnorm dvsr:testjneshlrclrclrcljmpword ptr [di][6], 8000hnorm dvdndword ptr [di][0], 1word ptr [di] [2], 1word ptr [di] [4], 1word ptr [di] [6], 1norm_dvsrnorm dvdnd:cmpbl, 4hjbeaddjmpchk 2cl, 10hready_dvdndcmpjaesubbl, 2hready_dvdndcl, 10h;we want to keep;the divisor;truly normalized;for maximum;precision;this should normalize dvsr;bx still contains pointer;to dvsr;adjust for wordchk_2:ready_dvdnd:leaorjeorjnsnegsubjmpdi, word ptr dvdndcl, clmakedeltacl, cldo_dvdnd_rightclch, chdo_dvdnd_leftdo_dvdnd_right:shrrcrword ptr [di][6], 1word ptr [di][4], 1useable informationrcrrcrloopsubororororword ptr [di][2], 1word ptr [di] [0], 1do_dvdnd_rightax, axax, word ptr [di][6]ax, word ptr [di][4]ax, word ptr [di][2]ax, word ptr [di][0];adjusting again for size;of shift;no adjustment necessary;no error on underflow;unless it becomes zero,;there may still be some;this should normalize dvsr119NUMERICAL METHODSrepjnemovmovstoswjmpdo_dvdnd_leftshlrclrclrcljcsetupdi, word ptr quotientcx, 4divmul exitword ptr [di] [0],word ptr [di][2],word ptr [di][4],word ptr [di][6],ovrflw;if it is now a zero,;that is the result1111loopdo dvdnd_leftmovmovmovmovswsi, didi, word ptr quotientcx, 4;significant bits;shifted out;data unusable;this should normalize dvsrsetup:rep;put shifted dividend;into quotientmakedelta:rep;this could be done with;a tablelealeamovmovswsi, word ptr dvsrdi, word ptr deltacx, 4notnotnotnegwordwordwordwordjcaddadcadcmloopword ptr delta[2], 1word ptr delta[4], 0word ptr delta[6], 0invokemu164, delta, dvsr, addr temp;move normalized dvsr;into deltaptrptrptrptrdelta[6]delta[4]delta[2]deltamloop:120;attempt to develop with;2's complementREAL NUMBERSrepreplealeamovmovswsi, word ptr temp[8]di, word ptr tmpcx, 4invokeadd64, tmp, dvsr, addr dvsrleamovmovmovswinvokedi, word ptr divisorsi, word ptr quotientcx, 4subcmpjbaddadcadcadcno_round:repmu164, delta, divisor, addr tempax, axword ptrno_roundword ptrword ptrword ptrword ptrtemp[6], 8000h;an attempt to round;.5 or above rounds uptemp[8], 1temp[l0], axtemp[l2], axtemp[l4], axlealeamovmovswinvokesi, word ptr temp[8]di, word ptr tmpcx, 4decjejmpbyte ptr lpdivmul_exitmakedeltasubnotmovmovstoswjmpax, axaxcx, 4di, word ptr quotient;double dutyadd64, divisor, tmp, quotient;six passes for 64 bitsovrflw:repdivmul_exit:popfretdivmul;make infinite answerdivmul exitendp121NUMERICAL METHODS1Van Aken, Jerry, and Ray Simar.
A Conic Spline Algorithm. Texas Instruments,1988.2Van Aken, Jerry, and Carrel Killebrew Jr. The Bresenham Line Algorithm.Texas Instruments, 1988.3Cavanagh, Joseph J. F. Digital Computer Arithmetic. New York, NY: McGrawHillBook Co., 1984, Pages 278-284. Also see Knuth, D. E. SeminumericalAlgorithms. Reading, MA: Addison-Wesley Publishing Co., 1981, Pages.295-297.4Cavanagh, Joseph J. F. Digital Computer Arithmetic. New York, NY: McGrawHillBook Co., 1984, Pages 284-289.122Previous Home NextCHAPTER 4Floating-Point ArithmeticFloating-point libraries and packages offer the software engineer a number ofadvantages. One of these is a complete set of transcendental functions, logarithms,powers, and square-root and modular functions.
These routines handle the decimalpoint placement and housekeeping associated with arithmetic and even providesome rudimentary handles for numerical exceptions.For the range of representable values, the IEEE 754 standard format is compactand efficient. A single-precision real requires only 32 bits and will handle a decimalrange of 1038 to 10-38, while a double-precision float needs only 64 bits and has a rangeof 10308 to 10- 308. Fixed-point representations of the same ranges can require a greatdeal more storage.This system of handling real numbers is compact yet has an extremely widedynamic range, and it’s standardized so that it can be used for interapplicationcommunication, storage, and calculation.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
