Morgan - Numerical Methods (523161), страница 5
Текст из файла (страница 5)
The troubleis, we don’t always have access to the smallest part. Depending on the amount ofstorage available, we may be nowhere near the smallest part and have, instead of acomplete representation of a number, only an approximation. Many common valuescan never be represented exactly in binary arithmetic. The decimal 0.1 or one 10th,for example, becomes an infinite series of ones and zeros in binary(1100110011001100 ... B). The difficulties in expressing fractional parts completelycan lead to unacceptable errors in the result if you’re not careful.12NUMBERSThe radix point (the point of origin for the base, like the decimal point) exists onthe number line at zero and separates whole numbers from fractional numbers. Aswe move through the positions to the left of the radix point, according to the rules ofpositional notation, we pass through successively greater positive powers of thatbase; as we move to the right, we pass through successively greater negative powersof the base.In the decimal system, the number 999.999 in positional notation is929190.9-19-29-3And we know that base 10102 = 100101 = 10100 = 1It is also true that10-1 = .110-2 = .0110-3 = .001We can rewrite the number as a polynomial9*102 + 9*101 + 9*100 + 9*10-1 + 9*10-2 + 9*10-3Multiplying it out, we get900 +90 + 9 + .9 + .09 + .009which equals exactly 999.999.Suppose we wish to express the same value in base 2.
According to the previousexample, 999 is represented in binary as 1111100111B. To represent 999.999, weneed to know the negative powers of two as well. The first few are as follows:13NUMERICAL METHODS2-1 = .5D2 = .25D2-3 = .125D2-4 = .0625D-52 = .03125D-22-6 = .015625D2-7 = .0078125D2-8 = .00390625D2-9 = .001953125D2-10 = .0009765625D-112= .00048828125D2-12 = .000244140625DTwelve binary digits are more than enough to approximate the decimal fraction.999. Ten digits produce1111100111.1111111111 =999.9990234375which is accurate to three decimal places.Representing 999.999 in other bases results in similar problems.
In base 5, thedecimal number 999.999 is noted12444.4444141414 =1*54 + 2*53 + 4*52 + 4*51 + 4*50. + 4*5-1 + 4*5-2 + 4*5-3 + 4*5-4 + 1*5-5 +4*5-6 + 1*5-7 + 4*5-8 + 1*5-9 + 4*5-10 =1*625 + 2*125 + 4*25 + 4*5 + 4+ 4*.2 + 4*.04 + 4*.008 + 4*.0016+ 1*.00032 + 4*.000065 + 1*.0000125 + 4*.00000256+ 1*.000000512 + 4*.0000001024or625+ +250 + 100 + 20 + 4 + .8 + .16 + .032 + .0064 + .00032 + .000256 +.0000128 + .00001024 + .000000512 + .00004096 =999.999004569614NUMBERSBut in base 20, which is a multiple of 10 and two, the expression is rational.
(Notethat digits in bases that exceed 10 are usually denoted by alphabetical characters; forexample, the digits of base 20 would be 0 l 2 3 4 5 6 7 8 9 A B C D E F G H I J .)29J.JJC2x202 + 9x201 + 19x200. + 19x20-1 + 19x20-2 + 12x20-3 =2x400 + 9x20 + 19x1. + 19x.05 + 19x.0025 + 12x.000125or800 + 180 + 19. + .95 + .0475 + .0015 =999.999As you can see, it isn’t always easy to approximate a fraction. Fractions are a sumof the value of each position in the data type.
A rational fraction is one whose sumprecisely matches the value you are trying to approximate. Unfortunately, the exactcombination of parts necessary to represent a fraction exactly may not be availablewithin the data type you choose. In cases such as these, you must settle for theaccuracy obtainable within the precision of the data type you are using.Types of ArithmeticThis book covers three basic types of arithmetic: fixed point (including integeronly arithmetic and modular) and floating point.Fixed PointFixed-point implies that the radix point is in a fixed place within the representation. When we’re working exclusively with integers, the radix point is always tothe right of the rightmost digit or bit.
When the radix point is to the left of the leftmostdigit, we’re dealing with fractional arithmetic. The radix point can rest anywherewithin the number without changing the mechanics of the operation. In fact, usingfixed-point arithmetic in place of floating point, where possible, can speed up anyarithmetic operation.
Everything we have covered thus far applies to fixed-pointarithmetic and its representation.15NUMERICAL METHODSThough fixed-point arithmetic can result in the shortest, fastest programs, itshouldn’t be used in all cases. The larger or smaller a number gets, the more storageis required to represent it. There are alternatives; modular arithmetic, for example,can, with an increase in complexity, preserve much of an operation’s speed.Modular arithmetic is what people use every day to tell time or to determine theday of the week at some future point. Time is calculated either modulo 12 or 24—that is, if it is 9:00 and six hours pass on a 12-hour clock, it is now 3:00, not 15:00:9 + 6 = 3This is true if all multiples of 12 are removed.
In proper modular notation, thiswould be written:9 + 63, mod 12.In this equation, the signmeans congruence. In this way, we can make largenumbers congruent to smaller numbers by removing multiples of another number (inthe case of time, 12 or 24). These multiples are often removed by subtraction ordivision, with the smaller number actually being the remainder.If all operands in an arithmetic operation are divided by the same value, the resultof the operation is unaffected. This means that, with some care, arithmetic operationsperformed on the remainders can have the same result as those performed on thewhole number.
Sines and cosines are calculated mod 360 degrees (or mod 2radians). Actually, the input argument is usually taken mod /2 or 90 degrees,depending on whether you are using degrees or radians. Along with some method fordetermining which quadrant the angle is in, the result is computed from thecongruence (see Chapter 6).Random number generators based on the Linear Congruential Method usemodular arithmetic to develop the output number as one of the final steps.4Assembly-language programmers can facilitate their work by choosing a modulusthat’s as large as the word size of the machine they are working on.
It is then a simplematter to calculate the congruence, keeping those lower bits that will fit within the16NUMBERSword size of the computer. For example, assume we have a hexadecimal doubleword:and the word size of our machine is 16 bitsFor more information on random number generators, see Appendix A.One final and valuable use for modular arithmetic is in the construction of selfmaintaining buffers and arrays. If a buffer containing 256 bytes is page aligned-thelast eight bits of the starting address are zero-and an 8-bit variable is declared tocount the number of entries, a pointer can be incremented through the buffer simplyby adding one to the counting variable, then adding that to the address of the base ofthe buffer.
When the pointer reaches 255, it will indicate the last byte in the buffer;when it is incremented one more time, it will wrap to zero and point once again atthe initial byte in the buffer.Floating PointFloating point is a way of coding fixed-point numbers in which the number ofsignificant digits is constant per type but whose range is enormously increasedbecause an exponent and sign are embedded in the number. Floating-point arithmeticis certainly no more accurate than fixed point-and it has a number of problems,including those present in fixed point as well as some of its own-but it is convenientand, used judiciously, will produce valid results.The floating-point representations used most commonly today conform, to somedegree, to the IEEE 754 and 854 specifications. The two main forms, the long realand the short real, differ in the range and amount of storage they require.
Under theIEEE specifications, a long real is an 8-byte entity consisting of a sign bit, an 11-bitexponent, and a 53-bit significand, which mean the significant bits of the floatingpoint number, including the fraction to the right of the radix point and the leading one17NUMERICAL METHODSto the left. A short real is a 4-byte entity consisting of a sign bit, an 8-bit exponent,and a 24-bit significand.To form a binary floating-point number, shift the value to the left (multiply bytwo) or to the right (divide by two) until the result is between 1.0 and 2.0.
Concatenatethe sign, the number of shifts (exponent), and the mantissa to form the float.Doing calculations in floating point is very convenient. A short real can expressa value in the range 1038 to 10-38 in a doubleword, while a long real can handle valuesranging from 10308 to 10-308 in a quadword. And most of the work of maintaining thenumbers is done by your floating-point package or library.As noted earlier, some problems in the system of precision and exponentiationresult in a representation that is not truly "real"—namely, gaps in the number line andloss of significance. Another problem is that each developer of numerical softwareadheres to the standards in his or her own fashion, which means that an equation thatproduced one result on one machine may not produce the same result on anothermachine or the same machine running a different software package. This compatibility problem has been partially alleviated by the widespread use of coprocessors.Positive and Negative NumbersThe most common methods of representing positive and negative numbers in apositional number system are sign magnitude, diminished-radix complement, andradix complement (see Table 1- 1).With the sign-magnitude method, the most significant bit (MSB) is used toindicate the sign of the number: zero for plus and one for minus.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
