Algorithms are of central importance to the existence of minds.
– Vernor Vinge
Three concepts support almost all of mathematics: algorithm, function and equa- tion. You are certainly familiar with equations from school mathematics, where you almost certainly met functions as well. But the term algorithm is probably less famil- iar to you. This chapter is not a review of what you learned earlier and an extension to the concept of algorithm; rather, it is meant to take you beyond your previous studies to rethink the concepts that underlie these three mathematical basics.
Although the word algorithm is rarely named by your arithmetic and mathemat- ics teachers, the processes algorithms represent have been central to your mathemat- ical studies since the time you first dealt with numbers as a young child. Algorithms have pervaded your mathematical experiences for they are the recipes that assist you in carrying out mathematical processes. Yes, recipes! Algorithms are just like the recipe, the step-by-step instructions, you would follow in your kitchen to bake a cake.
When you count and record numbers beyond ten you use an algorithm. When you add and subtract, multiply and divide (with their rules for regrouping14 and indenting and bringing down digits) and when you process fractions (recall dividing by inverting and multiplying) you use algorithms, too many of them rote (that is, not justified) processes.
You have used functions as well. When you wrote an equation like y = 2x 3, you were expressing a function. If you identify an x value, say 5, you can identify the corresponding y value, 7 in this case, as a function of 5. That idea of “plugging in a value for x to get a unique y value” is the essence of function.
In this chapter you will be asked to think seriously about these concepts, for they will pervade all that will follow. They are especially useful when thinking about calculator and computer computations.
2.1 An unexpected algorithm
Here is a deceptively simple question: How does your calculator accept the numbers you key in?
Suppose, for example, you wish to enter the number 342. You certainly know how to do that. You simply punch the keys 3, 4 and 2 in succession and then usually a key like + to continue a process. No problem.
Well, not quite. 342 = 300 + 40 + 2. How does the calculator know that the 3 you first pressed represents 300 and not just 3 or 30 or even 3000? Although we all write numbers from left to right, their value is determined from right to left. For the number 342, for example, you start on the right to assign 2 units, then 4 tens and finally 3 hundreds. If you fail to see this point for such a small number, consider how you would determine the value the 5 contributes to the number 5268433207. If you don’t start counting places from the right, you have a system of which I am unaware.
What you need is an algorithm that assigns a value to the number as you press those keys representing the digits. It turns out that the algorithm to carry this out is, once you think about it, transparently simple. You need only consider the process step-by-step in order to develop that procedure.
Step 1. You press the 3 key. At this point the calculator value is 3 and, if you next press a + or x or some other operation key, your calculator will know that 3 was the number you wished represented internally.
Step 2. In this case, however, it is not. The next key you press is 4, another digit, so the calculator must change its mind. Now the number it must consider is 34. How did it arrive at that? It shifted the 3 to the left and appended the 4. Again, if you next pressed an operation key, the calculator would operate on the resulting number, 34.
Step 3. But again you are not ready to calculate. You press the 2 key. And now the 34 is shifted to the left to make room for the 2 and you have 342.
That phrase “shift to the left” is exactly like the shift you use in multiplying by numbers with two or more digits, and the mathematical process it hides is the same one: it is accomplished by multiplication by 10. It is multiplication by 10 that changes 3 into 30 in Step 2 and 34 into 340 in Step 3.
Using that idea, you can generalize how those steps work in order to turn them into an algorithm.
Step 1. A digit key is pressed (in our example the digit 3.)
Step 2. If the next key pressed is also a digit, the earlier number is multiplied by 10 and the new number is added. (Keying the 4 then gave us 3 × 10 + 4 = 34.)
Step 3. Repeat Step 2 until a non-digit key is pressed; then continue with further calculation. (In our case keying 2 gave us 34 × 10 + 2 = 342.)
Panel 2.1.1:
Entering Numbers One Digit at a Time
Experiment with Panel 2.1.1 to see this process in operation. It uses this 10x + y process to show how this process works.
There can hardly be a better example of an algorithm than a calculator program. It is certainly a recipe that, when executed, carries out a process, sometimes a simple process like this one, but more often a complex process that saves a remarkable amount of time and effort on your part. A scientific calculator has literally hundreds of these built-in programs. Because users simply press keys and get answers, it is easy for them to forget the carefully designed programs that give even the simplest calculators the power to produce accurate results. For example, consider what happens when you key sin 2 3 ) ENTER into a scientific calculator. The resulting ten-digit value, .3907311285, doesn’t appear by some kind of magic: there is a programmed algorithm that produces that result.15
By asking you to think about how numbers are entered in a calculator or com- puter, I have raised the issue of representing numbers left to right and right to left. It is instructive to compare these two ways of considering numbers algebraically. In our usual terminology we think of 342 as 3 x 100 + 4 x 10 + 2. Following our algorithm, however, this number is represented differently. It becomes successively:
and we have 342 = (3 x 10 + 4) x 10 + 2. For larger numbers this new processing uses many parentheses. For example,
56, 832 = (((5 × 10 + 6) × 10 + 8) × 10 + 3) × 10 + 2
This is slightly shortened if we recall the alternative representation:
a × b = (a)b: 56, 832 = (((5 × 10 + 6)10 + 8)10 + 3)10 + 2
(2.1.1) There is a convenient way to carry out this process. It is called synthetic sub- stitution. You may have met this procedure in school but still not recognize this application. In the case of the last example, 56,832, the processing would look like the following.
First write 10 representing the decimal base, and separately the digits in the number, 56832. Below this leave space and draw a horizontal line:
Now start the process by simply bringing down the first digit, in this case 5:
Next multiply the 5 in the lowest row by the 10 base and record the product, 50, under the 6:
Add this second column and place the sum (56) below it. Notice that this multipli- cation and addition corresponds to the algorithm step: 5×10 + 6.
Continue to repeat these two steps – multiply by 10 up to the right, then sum down. If you follow the algorithm with care, your final result should look like this:
and the number you seek is at the end of the process. Note that this procedure avoids employing all those parentheses.
You have seen that decimal integers can be written in two forms. Polynomials may similarly be written in these two forms. Thus, for example,
You can check this by multiplying out those parentheses of the right side one at a time, of course working from the inside out. And this too may be developed by synthetic substitution but with x replacing the 10 of our decimal example:
You have seen here how the apparently simple act of entering a number in your calculator leads to some unexpected mathematical processing. In exercises 2.1.5 to 2.1.7 you will see that this number processing will be useful in different contexts.
Exercises 2.1
(2.1.1) Use Panel 2.1.1 to follow the steps entering the following numbers:
(a) 342 (b) 676767 (c) 123456
(2.1.2) Using equation (2.1.1) as a model, express each of the following in the left-to-right form:
(a)3246 (b) 706 (Be sure to include that )
(2.1.3) Using equation (2.1.2) as a model, express each of the following in the left-to-right form:
(a) 2x3 + 5x2 − 3x + 14
(b) 22x5 − 5x4 + 3x3 + 9x − 7 (Note that the x2 term is missing.)
(2.1.4) Use synthetic substitution to develop the number 22467 from left to right.
(2.1.5) It turns out that synthetic substitution has another useful purpose. Suppose you wish to find the y value for the equation y = 2x3 – 5x2 + 3x – 7 when x = 2. One way of doing this is simply to plug 2 into the equation in place of each x. Another way that simplifies some of the processing, is to use synthetic substitution. The coefficients of x in the polynomial serve as the values in the first line and 2 would play the role of the number to be substituted. That top line would appear as:
2 ) 2 -5 3 -7 and the final remainder would be the y-value you seek.
(a) Find y for that equation by plugging in x = 2 and simplifying.
(b) Use synthetic substitution to do this.
(c) Which approach seems easier?
(d) Which would be easier for a 5th degree polynomial?
Panel 2.1.2:
Evaluating Polynomials by Synthetic Substitution
(2.1.6) Panel 2.1.2 carries out synthetic substitution for you. Use Panel 2.1.2 to evaluate y or f (x) for the given x:
(a) y = 2x3 − 5x2 + 3x − 7 when x = 2
(b) f (x) = 3x5 − 25x4 + 5x3 − 29x2 + 4x − 3 when x = 7
(c) y = 5x3 – 4 when x = – 7 (Note that there are some zero coefficients in this equation and each of them must be entered.)
(d) f (x) = x8 + x7 + x6 + x5 + x4 + x3 + x2 + x + 1 for x = 2.
(e) y = x9 − 1 for x = 2. (Remember the warning in (c).)
(2.1.7) Exercise 2.1.6 (d) suggests a way to change binary numbers to decimal numbers for binary numbers are polynomials in powers of 2, just as decimal numbers are polynomials in powers of 10. Use Panel 2.1.2 with x = 2, and the binary digits as coefficients to evaluate:
(a) 101bin. Your answer should be 5. Use it to check your use of the program.
(b) 110101bin (c) 111000111000111bin
2.2 An old school algorithm
When I went to school in what seems now about a hundred years ago, we learned an algorithm for calculating square roots. Like the other rote procedures we learned — long division, solving quadratic equations, bisecting angles — we didn’t refer to the process as an algorithm. It was just another procedure whose steps we had to memorize. We used that square root algorithm to do many calculations, for example to show that √4057.69 = 63.7.
The algorithm disappeared from most school curricula by about 1980 with the introduction of calculators, early enough that you – and very likely your parents and grandparents as well – were never exposed to it. I’ll show you how that algorithm works so that, if you are ever shipwrecked Robinson Crusoe-like on a desert island without a calculator, and for some reason you need to find a square root, you can use this method. More seriously, you can demonstrate it to your math major friends to show them something they don’t already know. Once I show you how to calculate square roots by this odd method, I will give you a bonus. I will explain why it works, something I was never told.
Please understand the point of what we will be doing. I want to show you how a complicated mathematical algorithm can be justified. You may, in the process, learn – at least temporarily – how to carry out the algorithm (perhaps to impress your friends) but that will be a bonus. It is not our goal here.
- Beginning at the decimal point and working to the left and right, separate the number whose square root you seek (formally the radicand) into pairs of digits.
Then place a decimal point where your answer will appear above the original decimal point.
Figure 2.2.1.
Square Root Algorithm: Step 1
A digit will appear in your answer above each of these pairs of digits in the radicand.
2. Find the nearest square less than or equal to the leftmost Write this square below and its square root above that pair.
Figure 2.2.2.
Square Root Algorithm: Step 2
3. Subtract and bring down the next pair of digits.
Figure 2.2.3.
Square Root Algorithm: Step 3
Notice how step 3 is similar to one of the steps in long division.
4. Multiply your partial answer (6) by 20 and place the product to the left of your remainder from the last step. This number will serve as your divisor in the next step.
Figure 2.2.4.
Square Root Algorithm: Step 4
5. Divide the remainder in step 2 (457) by your result in step 3 (120) just to get an integer value. Do three things with that quotient, 3: (1) place that 3 as the next digit in your answer, (2) add that 3 to your divisor (120) to get 123, and multiply that sum by the 3, placing the product, 369, below the remainder.
Figure 2.2.5.
Square Root Algorithm: Step 5
Sometimes, as in long division, your product will be too large and you will have to reduce your trial divisor.
6. Now the steps Go back to Step 3 and continue. The results of following these steps appear here:
Figure 2.2.6.
Square Root Algorithm: Finishing up
That was an algorithm in its worst sense: a rote procedure that you simply followed with no understanding why steps like “multiply by 20” work. We’ll come to why shortly. But it is important to point out that calculator and computer programs present a perfect vehicle to represent such a step-by-step procedure. Today, unless you find yourself marooned on a desert island without your calculator, you can simply press a few keys to get a ten-digit square root.
How the school square root algorithm works
There are three kinds of people, those who can count and those who cannot.
– bumper sticker
The world is also generally divided into two classes of people: one class accepts things as they are, the other is interested in how things work and why they operate as they do. For example, some people are satisfied simply to drive a car; others are interested in how the car works beyond simply burning fuel. School classrooms when I was a student (and later a teacher) were designed only for that first class of people: ”Here it is, just accept it.” Today, more often students and teachers seek answers to the question ”Why?” I invite you to join the second, more thoughtful class.
Hopefully, you had several questions about that algorithm. I once asked a former student if he could remember the square root process I had taught him ten years earlier. He responded, “That was the one with a 20 in it, wasn’t it?” That 20 was indeed a strange number by which to multiply, wasn’t it? And why two digits at a time instead of one? Those are the kinds of questions that intrigue mathematicians – and I hope you as well.
Let’s discharge that second question first. Why does a pair of digits in the radicand lead to a single digit in the square root? You should see this by considering some numbers and their corresponding squares:
Similarly, for values less than one, you have:
Thus, each pair of digits in the radicand corresponds to a single digit of the square root.
Now let’s see what the algorithm is doing. To do so,√we will consider it first as a problem in geometry. You should agree that finding 4057.69 is equivalent to finding the side of a square with area 4057.69. That is also the way the Greeks would have seen this problem 2300 years ago.
In other words, we are faced with this problem:
Figure 2.2.7.
The geometric equivalent of finding √4057.69
We know that 602 = 3600 < 4057.69 < 4900 = 702, so we can fit a 60 x 60 square inside this figure.
Figure 2.2.8.
We use up 602 = 3600 of the 4057.69
This corresponds to the first steps in the algorithm. We are left with the lighter part of the figure whose area is 4057.69 – 3600 = 457.69.
Figure 2.2.9.
Now comes what you might consider a trick. We need to deal with that L-shaped figure. (The Greeks called this shape a gnomon, a word pronounced with a silent g.) We rearrange the two rectangles and the square that make up this figure as in Figure 2.10.
Figure 2.2.10.
Rearrangement of the 457.69 area.
I have indicated on Figure 2.10 that x is the remaining side length after the 60 has been removed. Clearly x is small compared with the overall length of the rearranged rectangle in Figure 2.10, so we can use 120 as a first estimate of its length. And that tells us where that multiplying by 20 comes from in the algorithm. We have two rectangles and, since we are dealing with the next decimal place we must also multiply by 10. (In this case, for example, the 6 in your answer represents 60.)
Figure 2.2.11.
The figure also shows us why, when we divide 457 by 120 to get an estimate of the width, x, we must then add that x to get the length before multiplying by that same x to approximate the area of the rectangle. Notice that in the algorithm, you have subtracted a total of 3600 + 369 = 3969 from the original radicand to leave the 88.69 still to be addressed. Figure 2.12 then shows how this process continues.
Figure 2.2.12.
Rearrangement of the 88.69 area.
And this time your trial divisor is 126.0 to complete the problem.
Now let us explore the square root algorithm from an algebraic perspective. I will not go into the same detail as I did with the geometric argument. In fact, I will consider only a simple square root that you may know – and, if you don’t you can certainly find it with a calculator. I wish to find √1849.
To do so, I set √1849 = 10t + u, with t representing the tens digit of the answer and u the units digit. Now I square both sides of that expression. Recall that (a + b)2 = a2 + 2ab + b2, so I get:
1849 = 100t2 + 20tu + u2
What you should immediately notice about that expression is the appearance of our old friend from the algorithm, the number 20.
I can determine that t by considering only the 1800. Referring only to the first term of the right member temporarily, I ask what value of t will best satisfy 1800 ≈ 100t2. This is equivalent to t2 ≈18, so t = 4 will serve for the tens digit.
I plug this into equation (2.2.1) to get:
1849 = 100 · 42 + 20 · 4 · u + u2
which simplifies (partially) to:
1849 = 1600 + 20 · 4 · u + u2
Notice that this corresponds to the beginning of the algorithm:
I subtract 1600 from each member of the equation to give us:
249 = 20 · 4 · u + u2
which is equivalent to:
249 = u(80 + u)
and I have reached this point in the algorithm:
and I finish up the algorithm as I did before, with u = 3, first adding it, then multiplying by it as the algebra indicates.
This may by now seem like overkill to you. The point of all this, however, should not be missed. Math holds together. That rote process, a process known and used since the time when decimal digits were first introduced to Western civilization, has a logical basis. Like all of math, it does not simply work because someone tells you it does.
You will meet another, quite different, algorithm for finding square roots in Section 2 of Chapter 9.
Exercises 2.2
(2.2.1) Algorithms pervade your activities. You follow many of them without thinking. Write out in a few steps algorithms for the following:
(a) Preparing a sandwich.
(b) Finding your way from your home to the nearest airport.
(c) Organizing your day.
(d) Name a step in each of (a)-(c) that could be further broken down into additional algorithm steps.
(2.2.2) Algorithms also pervade our mathematical activities. Write out algorithm steps to carry out the following arithmetic processes:
(a) 49 + 23 (b) 52 – 37 (c) 376 ÷ 4
(2.2.3) Calculate each of the following by the school square root method:
(a) √8464 (b) √561.69 (c) √493.817284
(2.2.4) Use your calculator to check your work in exercise 2.2.3.
(2.2.5) A program that calculates square roots by the algorithm you have just met takes a total of 33 program commands to carry out its function. Although a few of those steps perform what programmers call housekeeping — like rounding the answer to the correct number of decimal places — that is more than many of the programs that carry out complex functions of this text.
(a) One thing that motivates mathematicians is How would that apply here?
(b) Another motivation for mathematicians is elegance. Scientists define elegance as “pleasingly simple and ingenious.” Do you think that the rote school procedure for finding square roots is elegant?
(c) Do you think that understanding how a procedure works improves the elegance of the procedure?
(2.2.6) Trial and error is another way to determine square root with a calculator without using the square root key. The algorithm is simple: to find √N, guess an answer, square your guess, compare the square with N, adjust your guess and repeat. Suppose, for example, you wanted to know √10. You know that the answer will be between 3 and 4, so begin with a guess of 3.5. Squaring 3.5 gives 12.25 which is greater than 10, so your guess is too large. Try 3.2: 3.22 = 10.24, still too large. 3.12 = 9.61, too small so you now know your answer is between 3.1 and 3.2. You can now try 3.152, and so on. Use this method to find the square root of each of the following accurate to 100ths. (Note that this requires you to calculate to 1000ths in order to correctly round your answer to 100ths.
(a) √3 (b) √20 (c) √.75223
(2.2.7) Still another program that calculates square roots is called Newton”s Method. It is based on a calculus procedure developed by the mathematician Isaac Newton. It will be studied in Chapter 9 and is included here only to compare it with the School Square Root Method. It takes only eight program steps to carry out its square root function. Would you consider Newton’s Method more elegant than the School Square Root method? Give an argument why it is and an argument why it is not.
2.3 Functions
In the old days when people invented a new function they had something useful in mind.
– Henri Poincare´
Sometimes mathematicians have come up with terrible names for concepts – wit- ness the names “irrational” and “imaginary” for numbers that are neither irrational nor imaginary in the usual senses of those words. Fortunately they more often name concepts that conform with our usual idea of the words. Function is one of those happier name choices. Its formal mathematical definition, while including some technical refinements, is not basically different from functions with which we are familiar. Our various bodily functions, for example, take inputs like air and food and produce blood, fat, insulin, and various other products to help us live.
Here is an edited version of the Wikipedia definition of function:
In mathematics, a function is a relation between a given set of elements called the domain and a set of elements called the codomain. The function associates each element in the domain with exactly one element in the codomain. An example of a function with the real numbers as both its domain and codomain is the function f (x) = 2x, which associates every real number with the real number twice as big. In a particular case, we can write f (5) = 10. There are many ways to describe or represent functions: a function may be described by a formula, by a plot or graph, by an algorithm that computes it, by arrows between objects, or by a description of its properties.
There is some technical jargon in that definition that you may never meet again: domain and codomain, for example. They simply supply words for what you start with (the domain) and what you end up with (the codomain). Hidden in that verbiage, however, is the key idea of a mathematical function: for each input element there is “exactly one element” in the output. Squaring is a perfectly valid function even though pairs of values give the same output: (−4)2 → 16 and 42 → 16; but square root is not a function, because 16 has two different square roots, 4 and -4, thus 16 → 4 and 16 → −4, which is not allowed. On the other h and, √x is a function because the radical sign allows only the positive square root: √16 = 4 only.16
You are almost certainly used to seeing functions in the form of some letter, often y, equal to some expression with one or more x’s in it, something like y = x2 – 5x. For a number of reasons, mathematicians often use the notation f (x) where that y appears and that function would be recorded as f (x) = X2 – 5x. You also saw that usage in the Wikipedia function example, f (x) = 2x, which for most purposes is the same as y = 2x. One of the values of the function notation, however, is suggested by the example that followed: f (5) = 10. Function notation allows you to represent the processing of different values of x.
There are, however, a few confusing aspects of this notation. Notice how, in that last paragraph, there were two different functions that were named f (x). That is not good practice. It would have been better to call one of them g(x) in order to differentiate them. The other thing that can be confusing is the fact that parentheses often serve to represent multiplication. Why then doesn’t f (x) = f x? The answer has to be that you can tell which is meant by the context.
A good way to think about the idea of a function is as a black box with a machine inside that crunches whatever is put in according to some rule for that particular box and produces a result. Here are two such boxes: one with a specific rule, the other for the general idea:
Figure 2.3.1.
FunctionBoxes
Be sure you understand that a calculator or computer often plays the role of a function machine just like the boxes of Figure 3.1.
Functions and equations
It is easy to confuse functions with equations because even the statements that define particular functions, like f (x) = x2 -1, are indeed equations. Informally at least, all you need for an equation is that equals sign. The function, however, is just that f . You can talk about it “on its own.” For example, you can ask, “Is f always positive?” This particular f as defined is not because f (x) is zero for x = 1 and x = -1 and negative for any x in the range -1 < x < 1.
Okay, the two are different, but it is quite easy to use functions to create equations. Given the f (x) = x2 -1 of the previous paragraph, we can make equations simply by setting f (x) equal to something. For example, if we choose to set f (x) = 3, then the result is the same as the equation x2 -1 = 3.
It is equally easy to create functions related to equations. If, for example, you have the equation 3x + 7 = x2 + 1, you could define functions g(x) = 3x + 7 and h(x) = x2 + 1 that are related by the equation g(x) = h(x). This procedure could be used to solve a more complex equation by graphing.
On the other hand, as you will see in what follows, it might be useful to modify that equation 3x+7 = x2+1 by standard techniques to form the equation x2−3x−6 = 0. Now you can consider the function j(x) = x2 − 3x − 6 when j(x) = 0, or, if you wish, y = x2 − 3x − 6 when y = 0.
Exercises 2.3
(2.3.1) Given the function, f (x) = 3x − 5, evaluate the following:
(a) f (7) (b) f (−3) (c) f (a + 5)
(2.3.2) To evaluate f ( f (x)), which is sometimes abbreviated f 2(x), you first calculate f (x), then find f of that value. For example, suppose f (x) = x2-1 and you want the value of f 2(3). You would calculate f (3) = 8 and then calculate f (8) = 63 for your answer.
For f (x) = x2 − 1 calculate
(a) f ( f (2)) (b) f 2(1) (c) f 2(t)
(2.3.3) Given the two functions f (x) = x2 and g(x) = x − 2, simplify:
(a) f (5) · g(7) (b) f (g(4)) (c) g( f (4)) (d) f (g(t)) (e) g( f (t))
(2.3.4) Based on the functions defined in (2.3.3), form equations in x for:
(a) f (x) = g(x) (b) f (x) − g(x) = 0 (c) f (g(x)) = 7 + x
(2.3.5) Based on your answers to (2.3.3), is it always true that f (g(x)) = g( f (x))?
2.4 How computers solve equations
Politics is for the present, but an equation is for eternity.
– Albert Einstein
There are, of course, many equations that do not fit those simple forms: equations with higher powers, equations with radicals and equations with trigonometric or logarithmic functions. Although I will give you a panel that will solve polynomial equations, this section is designed to give you insight into how these more complex equations may also be solved through the use of calculators or computers.
Panel 2.4.1
A Polynomial Equation Solver
Panel 2.4.1 will solve any polynomial equation like. 03x5 – x3 + 3.65x2 + x – 58 = 0. The limitation of Panel 2.4.1 to polynomial equations is only due to the problem of entering information.
The exercises for this section will give you an opportunity to solve equations using this panel. Here is how to use it. Suppose you have an equation that you are asked to solve, for example:
x5 − x = 2x3 + 1
(2.4.2) As a first step toward solving that equation using Panel 2.4.1, you need to modify it so that it is equal to zero and the powers of its terms are in decreasing order:
x5 − 2x3 − x − 1 = 0
(2.4.3) This is always easy to accomplish as it only involves adding or subtracting terms. Once you have this equation, you can open Panel 2.4.1 and follow the steps leading to a solution.
Panel 2.4.1 provides you with a very powerful tool: the means to solve any polynomial equation. Now let’s see how that program can perform its task. To do that for equation 2.4.3, I replace that right side 0 with y or f (x) to define a function that is clearly related to the original equation. We now have:
x5 − 2x3 − x − 1 = y
(2.4.4) To help you see what is going on here, I will show you a graph of that function. This graph is not part of the solution technique, but it will help you to understand how that solution process works. Figure 2.4.1 shows the graph of the function in (2.4.4) that we seek to solve.
Figure 2.4.1
Now think about what we have done. We replaced 0 with y so any solutions or roots of equation (2.4.1) will appear on the graph when y = 0. Of course y = 0 when the graph crosses the x-axis and you can see immediately that equation (2.4.2) has three solutions that are located -2 < x1 < -1, -1 < x2 < 0. and 1 < x3 < 2. And if we can design a way to locate those x-axis crossings, we will have a way to solve our equation.
Suppose, for example, we wish to find that positive solution, not knowing any- thing about its value. What we are trying to do is locate the x-value of that point where the graph crosses the x-axis, that is, where y = 0. Even if we don’t have a graph like Figure 2.4.1 to help us, we can start by substituting integer x-values: 0, then 1, then 2, and so on in function (2.4.2). We know that if one of these x-values produces a y-value of 0, we will have a solution. Unfortunately, in this case we can see from the graph that that approach will not locate a solution because the graph crosses the x-axis between integers. (In fact, none of the solutions are integers.)
What we should notice, however, is that the value of y changes from positive to negative or negative to positive when we pass a solution. (Fortunately, we’re going to have a computer doing all this checking.)
We know from Figure 2.4.1 that the graph changes from negative to positive between x = 1 and x = 2. That tells us that the positive solution is x = 1 followed by some decimal values. Now we can proceed between x = 1 and x = 2 by taking smaller increments, x = 1.1, x = 1.2, and so on, testing each by substituting each x-value in the function again looking for a change in sign for the corresponding value of y. For equation (2.4.4) here is a summary of what we would find for three decimal places:
With that series of results, the value of x would round to 1.62. The program of Panel 2.4.1 carries out this kind of procedure to gain extreme accuracy. Despite all the hundreds or even thousands of calculation required, your panel will produce answers very quickly. This provides another example of the power that today’s computing gives you. Just fifty years ago such calculations would have taken hours or even days.
We are, however, still left with a question: How did the panel come up with those ”Yes” or ”No” answers. There is no little robot in your computer that can look at that graph I drew to answer those questions. Instead the calculator must use a mathematical check. Fortunately, that check turns out to be based on some very simple algebra.
I remind you of those rules for products of integers (often called informally “products of signed numbers”): When multiplying two factors, if the signs of the factors are the same, the product is positive; if the signs are different, the product is negative. Some (hopefully familiar) examples: −3 × −5 = +15, −3 × 5 = −15, 3 × 5 = 15 and 3 × −5 = −15. This is summarized in the following table.
The computer does not look at the graph; instead it evaluates the function at succes- sive x-values. For example, for the function of our example, when x = 0, y = -1 and when x = 1, y = 3, thus the product of those y-values is positive so the function does not (usually) cross the x-axis in that interval. But when x = 2, y = 13 and the product of the y-values for x = 1 and x = 2 is 3 13 = 39 which is negative, so the function crosses the x-axis in that interval and a solution is located there in the interval 1 < x < 2.Thus the solution begins with 1. followed by some decimal values.
Here in summary are the four situations that normally prevail.17
Figure 2.4.2
Function values within intervals
All the computer has to do is to multiply those function values, looking for the first negative product.
A different method of finding a root of an equation is by squeezing in on it. Suppose you were using this method to find the root of equation 2.4.1. (We already know that its root is 1.62 from our earlier work.) Let’s see how this approach would work if we started with a guess that the root is between x = 0 and x = 4. We proceed by bisecting the interval and choosing the half in which the root lies: In this case we would have: (Recall that the program is looking for that solution 1.62.)
Beginning with 0 < x < 4
Is the root in the interval 0 < x < 2 or2 < x < 4?
Answer: 0 < x < 2
Is the root in the interval 0 < x < 1 or1 < x < 2?
Answer: 1 < x < 2
Is the root in the interval 1 < x < 1.5 or 1.5 < x < 2?
Answer: 1.5 < x < 2
Is the root in the interval 1.5 < x < 1.75 or 1.75 < x < 2?
Answer: 1.5 < x < 1.75
Is the root in the interval 1.5 < x < 1.625 or 1.625 < x < 1.75?
Answer: 1.5 < x < 1.625
Is the root in the interval 1.5 < x < 1.5625 or 1.5625 < x < 1.625? Answer: 1.5625 < x < 1.625 and so on.
At this point we already know the solution accurate to two digits, x = 1.6, and the method could continue to find more accuracy. Notice that at each step the interval we seek is divided in half or bisected. Thus this approach is often called interval bisection.
I don’t want you to leave this topic thinking that the equation solving method of Panel 2.4.1 only applies to polynomial equations. I have used those as examples only because their equations are easy for you to enter by simply recording their coefficients. Here is an equation that is much more complicated:
That is, of course, a very artificial equation. I have made it up to illustrate the fact that these algorithms find answers to such involved — and to many people (perhaps you included) very frightening — equations.
We proceed just as we did with the polynomial example. Convert it so that it is equal to zero:
and replace that 0 with f (x) or y to define a function:
From here a computer or calculator equation solving program would proceed just as we have done here for polynomial roots, seeking where the function graph crossed the x-axis.
A Logistical Reminder
In the exercises you will be asked to solve some polynomial equations through use of Panel 2.4.1. They will work for general polynomials of the form:
Axn + Bxn−1 + Cxn−2 + … + Px + Q = 0
(2.4.7) in which those coefficients are any real numbers. And do not forget to include 0 as the coefficient of a missing power. Thus, for example, the equation of our example, x5 − 2x3 − x − 1 = 0, has coefficients: 1, 0, -2, 0 -1 and -1.
Exercises 2.4
(2.4.1) Use the program of Panel 2.4.1 to solve the following polynomial equations:
(a) 3x 7 = (You can easily solve this equation without using a program. Use that knowledge to check the panel algorithm.)
(b) x3 89 = Note that you are finding the cube root of 89. And don’t forget those 0 coefficients.
(c) x2 − 21x + 38 = 0.
(d) x4 − 3x2 = 12.
(e) 3x5 + 7x2 = 23x4 + 12x2 + 1.7x + 31.
(2.4.2) I used a graph to introduce the idea that equation solutions are found for the equation y = f (x) when y = 0. This raises a question: How does a computer draw a graph? Think about what you learned in this section to suggest an answer to that question.
(2.4.3) A serious problem arises when using the crossing-the-axis approach of this section you have an equation like x2 – 6x + 9 = 0. You can see by direct substitution that x = 3 is a solution. But the technique we have described does not find that solution. The problem is that the graph is as is shown in Figure 2.4.3. What happens when the computer looks for a sign change? More sophisticated programs like that of our Panel 2.4.1 take care of this case.
Figure 2.4.3
Graph of y = x2 − 6x + 9
(2.4.4) These questions relate to interval bisection:
(a) Suppose you are challenged to find an integer between 1and 100 inclusive — that is, the 1 and the 100 are included. You are given an opportunity to ask a series of questions, like ”Is the number less than 73?” or ”Is the number odd?” What is the least number of questions you need to ask to be certain that you have identified a particular number.
(b) By using interval bisection and splitting the available possibilities in half with each question, with 20 such questions you could find a single integer from a range of integers from 1 to N. Quickly guess the value of N.
(c) Now find N. (Suggestion: Consider starting from one question.)
(d) Comment on the comparison of your answers to (b) and (c).
Figure 2.4.4
Answers for Chapter 2.
