Getting ready

You should already have a directory for this class. Open a terminal window and cd into it. Make a new directory lab3 for today’s work with the mkdir command, and then change your directory again into it.

You’ll be working today in a file lab3.py; so fire up IDLE to edit it. Fill in the standard beginning comment.

Finding a zero by bisection

Today we will work on our first numerical problem, that of find a zero of a (real-valued) function, using the method of bisection—something you probably have done in an algebra class at some point.

The problem can be stated as:

The bisection algorithm works by finding the midpoint of the interval, figuring out in which half of the interval the function crosses zero, and continuing with that half as the new interval. The process continues until the interval is smaller than ϵ.

As a first exercise, try writing out the above algorithm (on paper!) as pseudocode. Feel free to compare notes with your classmates.

Once you have the basic algorithm written down, your job is to translate it into Python and ensure that it works. Write it as a Python function

Note something neat about this: you can actually pass a function as a parameter to another function! You will provide the name of a function as an actual parameter in a call to find_zero().

For testing, write a couple of additional functions that you can pass to find_zero(), and provide a test_find_zero() does several test cases and prints out the results (along with correct answers). As in last week’s lab, you’re likely to find it useful to write a function that does one test case that you can call from your main testing function.

You may encounter a few things you’ve overlooked as your translate your algorithm into Python and do your testing. That’s normal; it is a good idea to keep some notes about that as you go.

Documentation

If you haven’t already, be sure that each of your functions has a good “docstring”. Here are the conventional rules for docstrings:

• Enclose the docstring in triple quotes.
• The first line should be a one-line sentence in the imperative voice that says what the function does. For many functions, the verb will be “Return”.
• If you wish to say more, leave a blank line, then write however many paragraphs you need. Indent each line to match the quotes.
• Close with the triple quote on a line by itself, indented to match.

For our function, a suitable docstring might begin

It would probably be good if it also mentioned the method used (bisection), and anything else that someone using the function would need to know.

Testing

As you plan your testing and write functions to use as test cases, it would probably be good to include what the (known) zeros are as part of the extended docstring.

If you want to use some standard mathematical functions in your test functions, you can probably get them from the module math. The simplest way to do that will be to add the line

up before the first function definition, so that you can then use the functions with qualified names such as math.cos. You can see what functions are available from within the interpreter by

If you want a shorter list of just the names defined in math, you can use dir(math), then use (for example) help(math.cos) to find out details about a specific function.

Produce several test functions and document at least one zero for each. Feel free to share your tests with each other, but give credit for those you get from other members of the class.

Writing your function

Now it is time to go back and fill in the body of your primary function. Be sure to save it occasionally. You can use the “Run” menu to check it or run it in the interpreter. You probably want to arrange your windows so that you can see at least the left part of the xterm from which you launched IDLE, because some of the error messages will show up there.

Note that when you run your file, all it does is define the functions. You will still need to make various calls to actually do the tests.

Dealing with bad arguments

Python has nice features for dealing with exceptional conditions, such as when the function f blows up or when f(a) and f(b) have the same sign. We need to get some more experience to use those features, however.

Add assert statements to your find_zero() to check that a call satisfies its preconditions. You may find it useful to add other assertions to catch wierd cases.

A caution about floating-point

Recall that floating-point values have limited precision, and so are always approximations. That means that it is rarely a good idea to compare a computed floating-point value for equality; numerical calculations usually instead are designed to produce an approximation within a tolerance. That is the role of ϵ in our description.

Tracking down problems

You may find it helpful to insert print statements in your function to help you see what is going on as it iterates. We’ll learn soon how to use a debugger to inspect (and pause) a program during execution.

Finishing up

If everything works, congratulations! You now have a rough draft.

Go back and look closely at your functions, especially find_zero(). Are there any points at which you can make it clearer? Can you make it significantly more efficient? Polish your program. Use your test function to make sure that it still works correctly.

Finally, add a big string to the end of your program file (triple-quoted, like the docstring). In that string, summarize what you’ve learned today. Were there particular obstacles, surprises or oversights? Things that turned out to be especially helpful or useful?

If you find it easier to work with a printed copy of your program, a good way to print it is the (Unix) command

Hand in a printed copy of your program. You may want to print a copy for yourself, too.