Morgan - Numerical Methods (523161), страница 3
Текст из файла (страница 3)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .373CONTENTSF: TRANS.ASM AND TABLE.ASM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407G: MATH.C............................................................................475GLOSSARY. . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485INDEX ................................................................................ 493Additional DiskJust in case you need an additional disk, simply call the toll-free number listedbelow. The disk contains all the routines in the book along with a simple C shell thatcan be used to exercise them. This allows you to walk through the routines to see howthey work and test any changes you might make to them. Once you understand howthe routine works, you can port it to another processor. Only $10.00 postage-paid.To order with your credit card, call Toll-Free l-800-533-4372 (in CA 1-800356-2002). Mention code 7137. Or mail your payment to M&T Books, 411 Bore1Ave., Suite 100, San Mateo, CA 94402-3522.
California residents please addapplicable sales tax.Why This Book Is For YouThe ability to write efficient, high-speed arithmetic routines ultimately dependsupon your knowledge of the elements of arithmetic as they exist on a computer. Thatconclusion and this book are the result of a long and frustrating search forinformation on writing arithmetic routines for real-time embedded systems.With instruction cycle times coming down and clock rates going up, it wouldseem that speed is not a problem in writing fast routines. In addition, mathcoprocessors are becoming more popular and less expensive than ever before and arereadily available. These factors make arithmetic easier and faster to use andimplement.
However, for many of you the systems that you are working on do notinclude the latest chips or the faster processors. Some of the most widely usedmicrocontrollers used today are not Digital Signal Processors (DSP), but simpleeight-bit controllers such as the Intel 8051 or 8048 microprocessors.Whether you are using one on the newer, faster machines or using a simpleeight-bit one, your familiarity with its foundation will influence the architecture ofthe application and every program you write. Fast, efficient code requires anunderstanding of the underlying nature of the machine you are writing for.
Yourknowledge and understanding will help you in areas other than simply implementingthe operations of arithmetic and mathematics. For example, you may want theability to use decimal arithmetic directly to control peripherals such as displays andthumbwheel switches. You may want to use fractional binary arithmetic for moreefficient handling of D/A converters or you may wish to create buffers and arrays thatwrap by themselves because they use the word size of your machine as a modulus.The intention in writing this book is to present a broad approach to microprocessor arithmetic ranging from data on the positional number system to algorithms for1NUMERICAL METHODSdeveloping many elementary functions with examples in 8086 assembler andpseudocode.
The chapters cover positional number theory, the basic arithmeticoperations to numerical I/O, and advanced topics are examined in fixed and floatingpoint arithmetic. In each subject area, you will find many approaches to the sameproblem; some are more appropriate for nonarithmetic, general purpose machinessuch as the 8051 and 8048, and others for the more powerful processors like theTandy TMS34010 and the Intel 80386. Along the way, a package of fixed-point andfloating-point routines are developed and explained.
Besides these basic numericalalgorithms, there are routines for converting into and out of any of the formats used,as well as base conversions and table driven translations. By the end of the book,readers will have code they can control and modify for their applications.This book concentrates on the methods involved in the computational process,not necessarily optimization or even speed, these come through an understanding ofnumerical methods and the target processor and application. The goal is to move thereader closer to an understanding of the microcomputer by presenting enoughexplanation, pseudocode, and examples to make the concepts understandable.
It isan aid that will allow engineers, with their familiarity and understanding of the target,to write the fastest, most efficient code they can for the application.2IntroductionIf you work with microprocessors or microcontrollers, you work with numbers.Whether it is a simple embedded machine-tool controller that does little more thandrive displays, or interpret thumbwheel settings, or is a DSP functioning in a realtime system, you must deal with some form of numerics. Even an application thatlacks special requirements for code size or speed might need to perform anoccasional fractional multiply or divide for a D/A converter or another peripheralaccepting binary parameters.
And though the real bit twiddling may hide under thehood of a higher-level language, the individual responsible for that code must knowhow that operation differs from other forms of arithmetic to perform it correctly.Embedded systems work involves all kinds of microprocessors andmicrocontrollers, and much of the programming is done in assembler because of thespeed benefits or the resulting smaller code size. Unfortunately, few referencesare written to specifically address assembly language programming. One of themajor reasons for this might be that assembly-language routines are not easilyported from one processor to another.
As a result, most of the material devotedto assembler programming is written by the companies that make the processors. The code and algorithms in these cases are then tailored to the particularadvantages (or to overcoming the particular disadvantages) of the product. Thedocumentation that does exist contains very little about writing floating-pointroutines or elementary functions.This book has two purposes. The first and primary aim is to present a spectrumof topics involving numerics and provide the information necessary to understandthe fundamentals as well as write the routines themselves.
Along with this information are examples of their implementation in 8086 assembler and pseudocodethat show each algorithm in component steps, so you can port the operation toanother target. A secondary, but by no means minor, goal is to introduce you3NUMERICAL METHODSto the benefits of binary arithmetic on a binary machine. The decimal numberingsystem is so pervasive that it is often difficult to think of numbers in any other format,but doing arithmetic in decimal on a binary machine can mean an enormous numberof wasted machine cycles, undue complexity, and bloated programs. As you proceedthrough this book, you should become less dependent on blind libraries and moreable to write fast, efficient routines in the native base of your machine.Each chapter of this book provides the foundation for the next chapter.
At thecode level, each new routine builds on the preceeding algorithms and routines.Algorithms are presented with an accompanying example showing one way toimplement them. There are, quite often, many ways that you could solve thealgorithm. Feel free to experiment and modify to fit your environment.Chapter 1 covers positional number theory, bases, and signed arithmetic. Theinformation here provides the necessary foundation to understand both decimal andbinary arithmetic. That understanding can often mean faster more compact routinesusing the elements of binary arithmetic- in other words, shifts, additions, andsubtractions rather than complex scaling and extensive routines.Chapter 2 focuses on integer arithmetic, presenting algorithms for performingaddition, subtraction, multiplication, and division.
These algorithms apply to machines that have hardware instructions and those capable of only shifts, additions,and subtractions.Real numbers (those with fractional extension) are often expressed in floatingpoint, but fixed point can also be used. Chapter 3 explores some of the qualities ofreal numbers and explains how the radix point affects the four basic arithmeticfunctions.
Because the subject of fractions is covered, several rounding techniquesare also examined. Some interesting techniques for performing division, one usingmultiplication and the other inversion, are also presented. These routines areinteresting because they involve division with very long operands as well as from apurely conceptual viewpoint. At the end of the chapter, there is an example of analgorithm that will draw a circle in a two dimensional space, such as a graphicsmonitor, using only shifts, additions and subtractions.Chapter 4 covers the basics of floating-point arithmetic and shows how scalingis done.
The four basic arithmetic functions are developed into floating-point4INTRODUCTIONroutines using the fixed point methods given in earlier chapters.Chapter 5 discusses input and output routines for numerics. These routines dealwith radix conversion, such as decimal to binary, and format conversions, such asASCII to floating point. The conversion methods presented use both computationaland table-driven techniques.Finally, the elementary functions are discussed in Chapter 6. These includetable-driven techniques for fast lookup and routines that rely on the fundamentalbinary nature of the machine to compute fast logarithms and powers.
The CORDICfunctions which deliver very high-quality transcendentals with only a few shifts andadditions, are covered, as are the Taylor expansions and Horner’s Rule. Thechapter ends with an implementation of a floating-point sine/cosine algorithmbased upon a minimax approximation and a floating-point square root.Following the chapters, the appendices comprise additional information andreference materials. Appendix A presents and explains the pseudo-random numbergenerator developed to test many of the routines in the book and includesSPECTRAL.C, a C program useful in testing the functions described in this book.This program was originally created for the pseudo-random number generator andincorporates a visual check and Chi-square statistical test on the function.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
