Morgan - Numerical Methods, страница 4

AppendixB offers a small set of constants commonly used.The source code for all the arithmetic functions, along with many ancillaryroutines and examples, is in appendices C through F.Integer and fixed-point routines are in Appendix C. Here are the classicalroutines for multiplication and division, handling signs, along with some of the morecomplex fixed-point operations, such as the Newton Raphson iteration and linearinterpolation for division.Appendix D consists of the basic floating-point routines for addition,subtraction, multiplication, and division, Floor, ceiling, and absolute valuefunctions are included here, as well as many other functions important to themore advanced math in Chapter 6.The conversion routines are in Appendix E.

These cover the format andnumerical conversions in Chapter 5In Appendix F, there are two source files. TRANS.ASM contains the elementary5NUMERICAL METHODSfunctions described in Chapter 6, and TABLE.ASM that holds the tables, equatesand constants used in TRANS.ASM and many of the other modules.MATH.C in Appendix F is a C program useful in testing the functions describedin this book.

It is a simple shell with the defines and prototypes necessary to performtests on the routines in the various modules.Because processors and microcontrollers differ in architecture and instructionset, algorithmic solutions to numeric problems are provided throughout the book formachines with no hardware primitives for multiplication and division as well as forthose that have such primitives.Assembly language by nature isn’t very portable, but the ideas involved innumeric processing are. For that reason, each algorithm includes an explanation thatenables you to understand the ideas independently of the code. This explanation iscomplemented by step-by-step pseudocode and at least one example in 8086assembler. All the routines in this book are also available on a disk along with asimple C shell that can be used to exercise them.

This allows you to walk through theroutines to see how they work and test any changes you might make to them. Onceyou understand how the routine works, you can port it to another processor. Theroutines as presented in the book are formatted differently from the same routines onthe disk. This is done to accommodate the page size. Any last minute changes to thesource code are documented in the Readme file on the disk.There is no single solution for all applications; there may not even be a singlesolution for a particular application. The final decision is always left to the individualprogrammer, whose skills and knowledge of the application are what make thesoftware work.

I hope this book is of some help.6Previous HomeCHAPTER 1NumbersNumbers are pervasive; we use them in almost everything we do, from countingthe feet in a line of poetry to determining the component frequencies in the periodsof earthquakes. Religions and philosophies even use them to predict the future. Thewonderful abstraction of numbers makes them useful in any situation.

Actually, whatwe find so useful aren’t the numbers themselves (numbers being merely a representation), but the concept of numeration: counting, ordering, and grouping.Our numbering system has humble beginnings, arising from the need to quantifyobjects-five horses, ten people, two goats, and so on-the sort of calculations thatcan be done with strokes of a sharp stone or root on another stone. These are naturalnumbers-positive, whole numbers, each defined as having one and only oneimmediate predecessor. These numbers make up the number ray, which stretchesfrom zero to infinity (see Figure 1- 1).Figure 1-1. The number line.7NextNUMERICAL METHODSThe calculations performed with natural numbers consist primarily of additionand subtraction, though natural numbers can also be used for multiplication (iterativeaddition) and, to some degree, for division.

Natural numbers don’t always suffice,however; how can you divide three by two and get a natural number as the result?What happens when you subtract 5 from 3? Without decimal fractions, the results ofmany divisions have to remain symbolic. The expression "5 from 3" meant nothinguntil the Hindus created a symbol to show that money was owed. The words positiveand negative are derived from the Hindu words for credit and debit’.The number ray-all natural numbers- b e c a m e part of a much greater schemaknown as the number line, which comprises all numbers (positive, negative, andfractional) and stretches from a negative infinity through zero to a positive infinitywith infinite resolution*. Numbers on this line can be positive or negative so that 35 can exist as a representable value, and the line can be divided into smaller andsmaller parts, no part so small that it cannot be subdivided. This number line extendsthe idea of numbers considerably, creating a continuous weave of ever-smallerpieces (you would need something like this to describe a universe) that finally givemeaning to calculations such as 3/2 in the form of real numbers (those with decimalfractional extensions).This is undeniably a valuable and useful concept, but it doesn’t translate socleanly into the mechanics of a machine made of finite pieces.Systems of RepresentationThe Romans used an additional system of representation, in which the symbolsare added or subtracted from one another based on their position.

Nine becomes IXin Roman numerals (a single count is subtracted from the group of 10, equaling nine;if the stroke were on the other side of the symbol for 10, the number would be 11).This meant that when the representation reached a new power of 10 or just becametoo large, larger numbers could be created by concatenating symbols. The problemhere is that each time the numbers got larger, new symbols had to be invented.Another form, known as positional representation, dates back to the Babylonians,who used a sort of floating point with a base of 60.3 With this system, eachsuccessively larger member of a group has a different symbol. These symbols are8NUMBERSthen arranged serially to grow more significant as they progress to the left. Theposition of the symbol within this representation determines its value. This makes fora very compact system that can be used to approximate any value without the needto invent new symbols.

Positional numbering systems also allow another freedom:Numbers can be regrouped into coefficients and powers, as with polynomials, forsome alternate approaches to multiplication and division, as you will see in thefollowing chapters.If b is our base and a an integer within that base, any positive integer may berepresented as:or as:ai * bi + ai-1 * bi-1 + ... + a0 * b0As you can see, the value of each position is an integer multiplied by the basetaken to the power of that integer relative to the origin or zero. In base 10, thatpolynomial looks like this:ai * 10i + ai-1 * 10i-1 + ... + a0 * 100and the value 329 takes the form:3 * 10 + 2 * 10 + * 10Of course, since the number line goes negative, so must our polynomial:ai * bi + ai-1 * bi-1 + ...

+ a0 * b0 + a-1 * b-1 + a-2 * b-2 + ... + a-i *b-iBasesChildren, and often adults, count by simply making a mark on a piece of paperfor each item in the set they’re quantifying. There are obvious limits to the numbers9NUMERICAL METHODSthat can be conveniently represented this way, but the solution is simple: When thenumbers get too big to store easily as strokes, place them in groups of equal size andcount only the groups and those that are left over. This makes counting easier becausewe are no longer concerned with individual strokes but with groups of strokes andthen groups of groups of strokes. Clearly, we must make the size of each groupgreater than one or we are still counting strokes.

This is the concept of base. (SeeFigure l-2.) If we choose to group in l0s, we are adopting 10 as our base. In base 10,they are gathered in groups of 10; each position can have between zero and ninethings in it. In base 2, each position can have either a one or a zero. Base 8 is zerothrough seven. Base 16 uses zero through nine and a through f. Throughout thisbook, unless the base is stated in the text, a B appended to the number indicates base2, an O indicates base 8, a D indicates base 10, and an H indicates base 16.Regardless of the base in which you are working, each successive position to theleft is a positive increase in the power of the position.In base 2, 999 looks like:lllll00lllBIf we add a subscript to note the position, it becomes:19 18 17 16 15 04 03 12 11 10This has the value:1*29 +1*28 +1*27 +1*26 +1*25 +1*24 +1*23 +1*22 +1*21 +1*20which is the same as:1*512 + 1*256 + 1*128 + 1*64 + 1*32 + 0*16 + 0*8 + 1*4 + 1*2 + 1*1Multiplying it out, we get:512 + 256 + 128 + 64 + 32 + 0 + 0 + 4 + 2 + 1 = 99910NUMBERSFigure 1-2.

The base of a number system defines the number of unique digitsavailable in each position.Octal, as the name implies, is based on the count of eight. The number 999 is 1747in octal representation, which is the same as writing:1*83 + 7*82 + 4*81 + 7*80or1*512 + 7*64 + 4*8 + 7*1When we work with bases larger than 10, the convention is to use the letters ofthe alphabet to represent values equal to or greater than 10.

In base 16 (hexadecimal),therefore, the set of numbers is 0 1 2 3 4 5 6 7 8 9 a b c d e f, where a = 10 andf = 15. If you wanted to represent the decimal number 999 in hexadecimal, it wouldbe 3e7H, which in decimal becomes:3*162 + 14*161 + 7*160Multiplying it out gives us:3*256 + 14*16 + 7*111NUMERICAL METHODSObviously, a larger base requires fewer digits to represent the same value.Any number greater than one can be used as a base.

It could be base 2, base 10,or the number of bits in the data type you are working with. Base 60, which is usedfor timekeeping and trigonometry, is attractive because numbers such as l/3 can beexpressed exactly. Bases 16, 8, and 2 are used everywhere in computing machines,along with base 10. And one contingent believes that base 12 best meets ourmathematical needs.The Radix Point, Fixed and FloatingSince the physical world cannot be described in simple whole numbers, we needa way to express fractions.

If all we wish to do is represent the truth, a symbol willdo. A number such as 2/3 in all its simplicity is a symbol-a perfect symbol, becauseit can represent something unrepresentable in decimal notation. That numbertranslated to decimal fractional representation is irrational; that is, it becomes anendless series of digits that can only approximate the original. The only way toexpress an irrational number in finite terms is to truncate it, with a corresponding lossof accuracy and precision from the actual value.Given enough storage any number, no matter how large, can be expressed asones and zeros. The bigger the number, the more bits we need.

Fractions present asimilar but not identical barrier. When we’re building an integer we start with unity,the smallest possible building block we have, and add progressively greater powers(and multiples thereof) of whatever base we’re in until that number is represented.We represent it to the least significant bit (LSB), its smallest part.The same isn’t true of fractions. Here, we’re starting at the other end of thespectrum; we must express a value by adding successively smaller parts.