In the last lab, you set up a working directory, which you should use again this time. Use the ‘ls’ and ‘cd’ commands to change your directory to the same place you worked last time. (Hint: it should contain a file p1.py that you made last time.)
This week, you’ll be making a file named lab2.py. You could start up IDLE, use the menus to get a new window, and then “Save as”. But you can also give a filename when you start IDLE, as in (assuming you are in the right directory),
Notice the ampersand at the end of the command. This tells the shell to run the command in the background—which means you immediately get a new shell prompt. This is a convenient thing to do with commands that, like IDLE, put all of their interaction in new windows.
It is very often helpful to include in a program some notes for other programmers—comments that aren’t really part of the program, but will help someone reading it to understand it. In Python, such comments begin with a ‘#’, and whatever follows on the line will be ignored by Python. That lets you write a note on the end of a line or, if you start the line with a ‘#’, make an entire line a comment.
Eventually, you’ll end up with enough files that you might forget what some of them contain. (I’ll have that problem even sooner, when all of you turn in your programs.) So it is a good habit to place identifying comments at the beginning of each file. For this class, you should always begin with something that looks like this:
Fill in the right information, of course, with your name, the assignment, and date. If additional description were needed, it could follow on additional lines. (We’ll add another comment line before these in a future lab.)
One of the oldest known algorithms is due to the Greek mathematician Euclid, for finding the greatest common divisor of two positive integers. In terms that correspond to the Python we know so far, we can say that
The first part of your assignment is to translate this into a Python function gcd(m, n) and to make sure that your function works correctly.
Once you’ve written the def line, the next thing should be what Python-natives call the “docstring”. There are a number of conventions that make docstrings more consistent—and also make it feasible for various tools to process them. To get started, observe the following:
For our function, a suitable docstring might be
You should be able to fill in the body of your function.
You probably are eager to try out your function. You could run the module and give a it a try. But it is a good idea to first take a minute to jot down some good test cases (along with the correct answers).
Run your module, and try calling gcd() with a few test cases. A useful thing to know: if your program gets into a situation in which it runs for a very long time, you can interrupt it by typing a “control-C” (hold down the Ctrl key and hit c).
This is also a good time to think about what could go wrong. What would happen if you called your function with a non-integer argument? Would would happen if one of the arguments were zero or negative?
Whenever we write a function, we usually have some assumptions about what must be true; we call these the preconditions for the function. In the docstring above, we say that m and n must both be positive integers. Calling gcd() with anything else is a programming error, and it would be good to catch that.
In Python, we can use the assert statement to check for errors in programming. This statement consists of the keyword assert followed by a Boolean expression that must be true at that point in the program. We would like to assert that m is an integer and that it is positive. We can do the first part using the built-in function isinstance(), which asks whether a value is of a particular type:
That lets us write the assertion
Add appropriate assertions to your gcd(), just after the docstring.
Save and run your module, and see what happens if you now call gcd() with illegal values.
Your function isn’t very complicated; so testing isn’t all that hard. If it were a more complicated function—or one that might need some changes in the future—it would be helpful to leave something behind to help later programmers1 to make sure they don’t mess it up. You could write your test cases in a comment, but it is even nicer if you write a function that will automate the testing.
Below gcd(), write a function testGcd() that will run your test cases, in each case printing out the test values, the result, and whether it is correct, producing something like this:
Because you’re doing the same thing for each test case, you should probably write a function that performs (and prints) one test case, and them make testGcd() call it several times with different arguments.
Some notes about print: If you want to print more than one value on a line, you separate them with commas. Normally, each print goes to the next line after printing its values; you can tell it to stay on the same line by ending the print statement with a comma.
You may find it helpful to insert print statements in your function to help you see what is going on as it runs. We’ll soon learn how to use a debugger to inspect (and pause) a program during execution.
Note that when you are testing testGcd(), you will need to insert an error into either gcd() or your test cases to make sure that the error case works correctly.
Now write a new function that does the same computation without using recursion—i.e., without calling itself. So that you can take advantage of your old testing framework, first change the name of your old gcd() to gcd1(); don’t forget to change the calls inside the function as well as the name in the def statement.
In your new gcd(m, n) you’ll need to use a while statement to get repetition; in its body you’ll need to set m and n to the correct new values.
Python allows multiple assignment, which makes this easier to write. You can write
to compute all of the right-hand sides with the old values of a and b before assigning those new values simultaneously to both variables.
Be sure your new function has a good docstring, and add appropriate assertions. The function preconditions should be the same as for your gcd1(), but you may also want to add an assertion at the beginning of the while loop’s body. When you write a loop, there will usually be something that is true every time you start the body; that assertion is called the loop’s invariant.
If you have some time to spare, take a look at your testGcd(). It probably has a bunch of function calls that are almost the same. It might be nice if you could just make a list of test cases—as, say, a list of tuples:
Without disturbing your old testing function, write another test function testGcd2() that uses a loop and list of cases to test.
If everything works, congratulations! You now have a rough draft.
Go back and look closely at gcd() and gcd1(). Are there any points at which you can make it clearer? Polish your program. Be sure that each function (including the ones you wrote for testing) has a good docstring. Use your test function to make sure that gcd() works correctly.
You can print a copy of your program on the lab printer with the (Unix) command
You’ll type that in the Unix shell, not inside IDLE.
Today, print out a copy and turn it in to me.
1Who could be you, later on.