Morgan - Numerical Methods (523161), страница 17
Текст из файла (страница 17)
This is where thinking in base 2 (evenwhen hex notation is used) can help. Scaling by 1,024 or any binary data type insteadof 1,000 or any decimal power can mean the difference between a divide or multiplyroutine and a shift. As you’ll see in a routine at the end of this chapter, dividing bya negative power of two in establishing an increment results in a right shift. Anegative power of 10, on the other hand, is often irrational in binary and can resultin a complex, inaccurate divide.Before looking at actual code, lets examine the basic arithmetic operations.
Theconversions used in the following examples were prepared using the computationaltechniques in Chapter 5.93NUMERICAL METHODSNote: The “.” does not actually appear. They are assumed and added by the authorfor clarification.Say we want to add 55.33D to 128.67D. In hex, this is 37.54H + 80.acH,assuming 16 bits of storage for both the integer and the mantissa:+37.54H80.acHb8.00H(55.33D)(128.67D)(184.00D)Subtraction is also performed without alteration:-80.acH37.54H49.58H(128.67D)(55.33D)(73.34D)37.54H80.acHb6.a8H(55.33D)(128.67D)(-73.34D)Fixed-point multiplication is similar to its pencil-and-paper counterpart:x80.acH37.548lbcf.2c70H(128.67D)(55.33D)(7119.3111D)as is division:÷80.acH37.54H2.53H(128.67D)(55.33D)(2.32D)The error in the fractional part of the multiplication problem is due to the lackof precision in the arguments.
Perform the identical operation with 32-bit precision,and the answer is more in line: 80.ab85H x 37.547bH = 1bcf.4fad0ce7H.94REAL NUMBERSThe division of 80acH by 3754H initially results in an integer quotient, 2H, anda remainder. To derive the fraction from the remainder, continue dividing until youreach the desired precision, as in the following code fragment:submovmovdiva, dxax, 80achcx, 37548cxmovsubdivbyte ptr quotient[l], alax, axcxmov;this divide leaves the quotient;(2) in ax and the remainder;remainder (1204H) in dx;Divide the remainder multiplied;by 10000H x to get the fraction;bits Overflow is not a danger;since a remainder may never be;greater than or;even equal to the divisor.byte ptr quotient[0], ah;the fraction bits are then 53H,;making the answer constrained;to a 16-bit word for this;example, 2.53H* The 8086 thoughtfully placed the remainder from the previous division in theDX register, effectively multiplying it by 10000H.Of course, you could do the division once and arrive at both fraction bits andinteger bits if the dividend is first multiplied by 10000H (in other words, shifted 16places to the left).
However, the danger of overflow exists if this scaling producesa dividend more than 10000H times greater than the divisor.The following examples illustrate how fixed-point arithmetic can be used inplace of floating point.A Routine for Drawing CirclesThis first routine is credited to Ivan Sutherland, though many others have workedwith it.’ The algorithm draws a circle incrementally from a starting point on the circle95NUMERICAL METHODSand without reference to sines and cosines, though it’s based on those relationships.To understand how this algorithm works, recall the two trigonometric identities(see Figure 3- 1):sin= ordinate / radius vectorcos= abscissa / radius vector(whereis an angle)Multiplying a fraction by the same value as in the denominator cancels thatdenominator, leaving only the numerator.
Knowing these two relationships, we canderive both the vertical coordinate (ordinate) and horizontal coordinate (abscissa)Figure 3-1. A circle drawn using small increments of t.96REAL NUMBERSin a rectangular coordinate system by multiplying sin by the radius vector for theordinate and cosby the radius vector for the abscissa. This results in the followingpolar equations:x(a) = r * cos ay(a) = r * sin aIncreasing values offrom zero toradians, will rotate the radius vectorthrough a circle, and these equations will generate points along that circle.
Theformula for the sine and cosine of the sum of two angles will produce those increasingvalues of by summing the current angle with an increment:Let a be the current angle and b the increment. Combining the polar equationsfor deriving our points with the summing equations we get:For small angles (much smaller than one), an approximation of the cosine isabout one, and the sine is equal to the angle itself. If the increment is small enough,the summing equations become:and then:97NUMERICAL METHODSUsing these formulae, you can roughly generate points along the circumferenceof a circle.
The difficulty is that the circle gradually spirals outward, so a smalladjustment is necessary-the one made by Ivan Sutherland:When you select an increment that is a negative power of two, the followingroutine generates a circle using only shifts and adds.circle: Algorithm1.Initialize local variables to the appropriate values, making a copy ofx and y and clearing x_point and y_point. Calculate the value for thethe loop counter, count.2. Get_x and_y and round to get new values for pixels.
Perform a de factodivide by l000H by taking only the value of DX in each case for the points.3. Call your routine for writing to the graphics screen.4. Get _y, divide it by the increment, inc, and subtract the result from_X.5.Get _x, divide it by inc, and add the result to _y.6.Decrement count.If it isn't zero, return to step 2.If it is, we're done.circle: listing; *****;;circle proc uses bx cx dx si di, x_ coordinate:dword, y_ coordinate:dword,increment:word98localx:dword, y:dword, x_point:word, y_point:word, countmovmovax, word ptr x_ coordinatedx, word ptr x_coordinate[2]REAL NUMBERSmovmovmovmovmovmovword ptrword ptrax, worddx, wordword ptrword ptrsubmovmovax, axx_point, axy__point, axmovmovmovax, 4876hdx, 6hcx, word ptr incrementget_num_points:shlrclloopmovset_point:movmovaddjncadcstore_x:movmovmovaddjncadcstore_y:movx, axx[2], dxptr y_coordinateptr y_coordinate[2]y, axy[2], dxax, 1dx, 1get_num_pointscount, dxax, word ptr xdx, word ptr x[2]ax, 8000hstore_xdx, 0h;load local variables;x coordinate;y coordinate;2 * pi;make this a negative;power of two;2 * pi radians;divide by 10000h;add .5 to round up;to integersx_point, dxax, word ptr ydx, word ptr y[2]ax, 8000hstore_ydx, Oh;add .5y_point, dx;your routine for writing to the screen goes here and uses x-point and;y_point as screen coordinatesmovmovax, word ptr ydx, word ptr y[2]99NUMERICAL METHODSmovupdate_x:sarsignrcrloopsubsbbcx, word ptr incrementmovmovmovupdate_y:sarsignrcrloopaddadcdecjnzax, word ptr xdx, word ptr x[2]cx, word ptr incrementdx 1ax, 1update xword ptr x, axword ptr x[2], dxdx, 1ax, 1update_yword ptr y, axword ptr y[2], dxcountset_point;arithmetic shift to maintain;new x equals x - y * increment;arithmetic shift to maintain;new y equals y + x * incrementretcircle endpBresenham’s Line-Drawing AlgorithmThis algorithm is credited to Jack Bresenham, who published a paper in 1965describing a fast line-drawing routine that used only integer addition and subtraction.2The idea is simple: A line is described by the equation f(x,y) = y’ * x-x’ * y fora line from the origin to an arbitrary point (see Figure 3-2).
Points not on the line areeither above or below the line. When the point is above the line, f(x,y) is negative;when the point is below the line, f(x,y) is positive. Pixels that are closest to the linedescribed by the equation are chosen. If a pixel isn’t exactly on the line, the routinedecides between any two pixels by determining whether the point that lies exactlybetween them is above or below the line. If above, the lower pixel is chosen; if below,the upper pixel is chosen.In addition to these points, the routine must determine which axis experiencesthe greatest move and use that to program diagonal and nondiagonal steps. It100REAL NUMBERSFigure 3-2. Bresenham’s line-drawing algorithm.calculates a decision variable based on the formula 2 * b+a, where a is the longestinterval and b the shortest.
Finally, it uses 2 * b for nondiagonal movement and 2 *b - 2 * a for the diagonal step.line: Algorithm1.Set up appropriate variables for the routine. Move xstart to x and ystartto y.2.Subtract xstart from xend.If the result is positive, make xstep_diag 1 and store the result inx dif.If the result is negative, make xstep_diag -1 and two's-complement the101NUMERICAL METHODSresult before storing it in x_dif.Subtract ystart from yend.3.If the result is positive, make ystep_diag 1 and store the result iny_dif.If the result is negative, make ystep_diag -1 and two's-complement theresult before storing it in y_dif.4.Compare x_dif with y_dif.If x_dif is smaller, swap x_dif and y_dif, clear xstep, and store thevalue of ystep_diag in ystep.If x_dif is larger, clear ystep and store the value of xstep_diag inxstep.5.Call your routine for putting a pixel on the screen.6.Test decision.If it's negative, add xstep to x, ystep to y, and inc to decision, thencontinue at step 7.If it's positive, add xstep_diag to x, ystep_diag to y, and diag_inc todecision, then go to step 7.7.Decrement x dif.If it's not zero, go to step 5.If it is, we're done.line: Listing;*****lineprocuses bx cx dx si di, xstart:word, ystart:word, xend:word, yend:wordlocalx:word, y:word, decision:word, x_dif:word, y_dif:word,xstep_diag:word,ystep_diag:word, xstep:word, ystep:word, diag_incr:word, incr:wordmovmovmovmovdirection:movsubjns102ax, wordword ptrax, wordword ptrptr xstartx, axptr ystarty, axax, word ptr xendax, word ptr xstartlarge_x;initialize local variables;total x distance;which direction are we drawing?REAL NUMBERSnegmovjmplarge_x:movstore xdif:movaxword ptr xstep_diag, -1short store xdifmovsubjnsnegmovjmplarge_y:movstore ydif:movax, word ptr yendax, word ptr ystartlarge_yaxword ptr ystep_diag, -1short store ydif;went negativeword ptr xstep_diag, 1x dif, ax;y distance;which direction?word ptr ystep_diag, 1word ptr y_dif, ax;direction is determined by signsmovmovcmpjgax, word ptr x difbx, word ptr y-difax, bxbigger x;the axis with greater difference;becomes our referencemovy_dif, ax;we have a bigger y move;than x;x won't change on nondiagonal;steps, y changes every stepoctant:movsubmovmovmovjmpbigger x:movx dif, bxax, axword ptr xstep, axax, word ptr ystep_diagword ptr ystep, axsetup incmovsubmovsetup inc:movshlmovword ptr xstep, axax, axword ptr ystep, axax, word ptr xstep_diagax, word ptr y difax, 1word ptr incr, ax;x changes every step;y changes only;on diagonal steps;calculate decision variable;nondiagonal increment; = 2 * y_dif103NUMERICAL METHODSsubmovax, word ptr x_difword ptr decision, axsubmovax, word ptr x_difword ptr diag incr, axmovax, word ptr decisionmovmovmovbx, word ptr xcx, word ptr x_difdx, word ptr y;dec is ion variable; = 2 * y_dif - x_dif;diagonal increment; = 2 * y_dif - 2 * x_dif;we will do it all in;the registersline loop:; Put your routine for turning on pixels here.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
