Morgan - Numerical Methods (523161), страница 8
Текст из файла (страница 8)
This and the next instruction can be very useful inan embedded system that receives decimal data and must perform some simpleprocessing before displaying or returning it.Decimal Adjust on Subtract. This instruction is similar to the preceeding oneexcept that it applies to subtraction.ASCII Adjust. These instructions prepare either binary data for conversion toASCII or ASCII data for conversion to binary. Though Motorola processors alsoimplement these instructions, they are found only in the 80x86 series in our list.Used correctly, they can also do a certain amount of arithmetic.30NUMBERSMost of the earlier microprocessors-such as the 8080, 8085, Z80, and 8086—as well as microcontrollers like the 8051 were designed with general applications inmind.
While the 8051 is billed as a Boolean processor, it’s general set of instructionsmakes many functions possible and keeps it very popular today.All these machines can do arithmetic at one level or another. The 8080, 8085, andZ80 are bit-oriented and don’t have hardware multiplies and divides, making themsomewhat slower and more difficult to use than those that do.
The 8086 and 8051have hardware multiplies and divides but are terribly slow about it. (The timings forthe 8086 instructions were cleaned up considerably in subsequent generations of the286, 386, and 486.) They added some speed to the floating-point routines anddecreased code size.Until a few years ago, the kind of progress usually seen in these machines wasan increase in the size of the data types available and the addition of hardwarearithmetic. The 386 and 486 can do some 64-bit arithmetic and have nice shiftinstructions, SHLD and SHRD, that will happily shift the bits of the second operandinto the first and put the number of bits shifted in a third operand.
This is done in asingle stroke, with the bits of one operand shifted directly into the other, easingnormalization of long integers and making for fast binary multiplies and divides. Inrecent years we’ve seen the introduction of microprocessors and microcontrollersthat are specially designed to handle floating-point as well as fixed-point arithmetic.These processors have significantly enhanced real-time control applications anddigital signal processing in general.
One such microprocessor is the TMS34010; amicrocontroller with a similar aptitude is the 80C196.31NUMERICAL METHODS1Kline, Morris. Mathematics for the Nonmathematician. New York, NY: DoverPublications, Inc., 1967, Page 72.2Gellert, W., S. Gottwald, M. Helwich, H.
Kastner, and H. Küstner (eds.). TheVNR Concise Encyclopedia of Mathematics. New York, NY: Van NostrandReinhold, 1989, Page 20.3Knuth, D. E. Seminumerical Algorithms. Reading, MA: Addison-Wesley Publishing Co., 1980, Page 180.4Knuth, D. E. Seminumerical Algorithms. Reading, MA: Addison-Wesley Publishing Co., 1981, Pages 1-127.5Cavanagh, Joseph J. F.
Digital Computer Arithmetic. New York, NY: McGrawHill Book Co., 1984, Page 2.6Pearson, Carl E. (ed.) Handbook of Applied Mathematics. New York, NY: VanNostrand Reinhold, 1983, Page 1.32Previous Home NextCHAPTER 2IntegersReducing a problem to the integer level wherever possible is certainly one of thefastest and safest ways to solve it. But integer arithmetic is only a subset of fixedpoint arithmetic. Fixed-point arithmetic means that the radix point remains in thesame place during all calculations.
Integer arithmetic is fixed point arithmetic withthe radix point consistently to the right of the LSB. Conversely, fractional arithmeticis simply fixed point with the radix point to the left of the MSB. There are no specificrequirements regarding placement of the radix point; it depends entirely on the needsof the operation. Sines and cosines may require no integer at all, while a power-seriescalculation may require an integer portion.
You may wish to use two guard digitsduring multiplication and division for rounding purposes-it depends on you and theapplication.To present algorithms for the four basic operations of mathematics-addition,subtraction, multiplication, and division-this chapter will concentrate on integeronly arithmetic. The operations for fixed-point and integer-only arithmetic areessentially the same; the former simply involves some attention to the placement ofthe radix point.This chapter begins with the basic operations and the classic algorithms for them,followed by some more advanced algorithms.
The classic algorithms aren’t necessarily the fastest, but they are so elegant and reflect the character of the binarynumbering system and the nature of arithmetic itself so well that they are worthknowing. Besides, on any binary machine, they’ll always work.Addition and SubtractionUnsigned Addition and SubtractionSimply put, addition is the joining of two sets of numbers or quantities, into oneset. We could also say that when we add we’re really incrementing one value, the33NUMERICAL METHODSaugend, by another value, the addend. Subtraction is the inverse of addition, with onenumber being reduced, or decremented, by another.For example, the addition operation+29or011100101001might be accomplished on the 8086 with this instruction sequence:movaddal,7al,2In positional arithmetic, each position is evaluatedx <base, with x being thedigit in that position, and any excess is carried up to the next position.
If the base is10, no number greater than nine can exist in any position; if an operation results ina value greater than nine, that value is divided by 10, the quotient is carried into thenext position, and the remainder is left in the current position.The same is true of subtraction except that any underflow in an operation resultsin a borrow from the next higher position, reducing the strength of that position byone. For example:17-981or000110011000In 8086 assembler, this would be:movSubal,llhal,9hOn a microprocessor, the carry and borrow use the carry flag. If adding any twounsigned numbers results in a value that cannot be contained within the data typewe’re using, a carry results (the carry flag is set); otherwise, it is reset. To demonstratethis, lets add two bytes, 7H and 9H:34INTEGERS0111+100110000 the result¦ the carryThis addition was unsigned and produced a result that was too large for the datatype.
In this case, the overflow was an error because the value represented in theresult was not the full result. This phenomenon is useful, however, when performingmultiprecision arithmetic (discussed in the next section).Subtraction will produce a carry on an underflow (in this case, it’s known as aborrow):10001-100101000 the result¦ the borrowProcessors use the carry flag to reflect both conditions; the trick is to know howthey’re representing the borrow. On machines such as the 8086, the carry is set forboth overflow from addition and underflow from subtraction. On the 80C196, thecarry is set on overflow and reset (cleared) on underflow, so it’s important to knowwhat each setting means. Besides being set or reset as the result of an arithmeticoperation, the carry flag is usually reset by a logical operation and is unaffected bya move.Because not every problem can be solved with single precision arithmetic, theseflags are often used in multiprecision operations.Multiprecision ArithmeticWorking with large numbers is much the same as working with small numbers.As you saw in the earlier examples, whenever we ADDed a pair of numbers the carryflag was set according to whether or not an overflow occurred.
All we do to add a verylarge number is ADD the least significant component and then ADD each subsequent35NUMERICAL METHODScomponent with the carry resulting from the previous addition.Let’s say we want to add two doubleword values, 99999999H and 15324567H.The sequence looks like this:m o v dx,9999hm o v ax,9999ha d d ax,4567ha d c dx,1532hDX now contains the most significant word of the result, and AX contains theleast. A 64-bit addition is done as follows.add64: Algorithm1.A pointer is passed to the result of the addition.2.The least significant words of addend0 are loaded into AX:DX.3.The least significant words of addend1 are added to these registers,least significant word first, using the ADD instruction. The next moresignificant word uses the ADC instruction.4.The result of this addition is written to result.5.The upper words of addend0 are loaded into AX:DX.6.The upper words of addend1 are added to the upper words of addend0 usingthe ADC instruction.
(Note that the MOV instructions don't change theflags.)7.The result of this addition is written to the upper words of result.add64: Listing; *****;add64 - adds two fixed-point numbers;the arguments are passed on the stack along with a pointer to storage for theresultadd64 proc uses ax dx es di, addendO:qword, addendl:qword, result:wordmovdi, word ptr resultmovax, word ptr addend0[0]; ax = low word, addend0movdx, word ptr addend0[2]; dx = high word, addend0addax, word ptr addendl[0]; add low word, addend1adcdx, word ptr addendl[2]; add high word, addend1movword ptr [di], axmovword ptr [di][2], dx36INTEGERSmovmovadcadcmovmovretadd64 endpax, worddx, wordax, worddx, wordword ptrword ptrptr addend0[4]ptr addend0[6]ptr addendl[4]ptr addendl[6][di][4], ax[di] [6], dx;;;;ax = low word, addend0dx = high word, addend0add low word, addend1add high word, addend1This example only covered 64 bits, but you can see how it might be expandedto deal with operands of any size.
Although the word size and mnemonics vary frommachine to machine, the concept remains the same.You can perform multiprecision subtraction in a similar fashion. In fact, all youneed to do is duplicate the code above, changing only the add-with-carry (ADC)instruction to subtract-with-borrow (SBB). Remember, not all processors (the 8048and 8051, for instance) have a simple subtract instruction; in case of the 8051, youmust clear the carry before the first subtraction to simulate the SUB.
With the 8048you must have two’s complement the subtrahend and ADD.sub64: Algorithm1.A pointer is passed to the result of the subtraction.2.The least significant words of sub0 are loaded into AX:DX.3.The least significant words of sub1 are subtracted fromthese registers,least significant word first, using the SUB instructions with the nextmost significant word using the SBB instruction.4.The result of this subtraction is written to result.5.The upper words of sub0 are loaded into AX:DX6.The upper words of sub1 are subtracted from the upper words of sub0 usingthe SBB intruction. (Note that the MOV instructions don't change theflags.)7.The result of this subtraction is written to the upper words of result.sub64: Listing;*****;sub64;arguments passed on the stack, pointer returned to result37NUMERICAL METHODSsub64 proc uses dx es di,sub0:qword, sub1:qword, result:wordmovdi, word ptr resultmovax, word ptr sub0[0]; ax = low word, sub0dx, word ptr sub0[2]mov; dx = high word, sub0subax, word ptr sub1[0]; subtract low word, sub1sbbdx, word ptr subl[2]; subtract high word, sub1movword ptr [di] [0],axmovword ptr [di] [2],dxmovax, word ptr sub0[4]; ax = low word, sub0movdx, word ptr sub0[6]; dx = high word, sub0sbbax, word ptr subl[4]; subtract low word, sub1sbbdx, word ptr subl[6]; subtract high word, sub1movword ptr [di][4],axmovword ptr [di][6],dxretsub64 e n d pFor examples of multiprecision addition and subtraction using other processors,see the SAMPLES.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
