Self-Study 2, CPSC 331, Fall 2010

home page -  news -  syllabus -  schedule -  assignments -  tutorials -  tests -  java -  references -  Mike Jacobson


Self-Study 1 -  Self-Study 2 -  Self-Study 3 -  Self-Study 4 -  Self-Study 5 -  Self-Study 6 -  Self-Study 7

 Applications of Proofs of Correctness

About This Exercise

This exercise has four objectives:

This exercise can be completed at any time after the first week of classes. You should work through it on your own as soon as possible after that.

Expected Background and Preparation

It is assumed that you have attended the first week of lectures and that you have been working through the material concerning Java in the textbook, and in online tutorials, that has been mentioned in previous exercises.

It is also assumed that you have completed the first self-study exercise, so that you are able to compile Java programs at school (and, if you wish, at home).

Problems To Be Solved

The Fibonacci numbers are a sequence of numbers whose properties have been studied since at least 200 B.C. For an integer i ≥ 0, the ith Fibonacci number, Fi, is defined as follows.

As we will see, their computation presents several programming challenges.

  1. The above definition of the Fibonacci numbers can used to produce a recursive algorithm to compute a given Fibonacci number, as shown below.

    Precondition: i is an integer such that i ≥ 0
    Postcondition: i is unchanged; value returned is the ith Fibonnaci number
    int fib ( int i ) {
       if ( i == 0 ) {
         return 0;
       } else {       // i ≥ 1
         if ( i == 1 ) {
           return 1;
         } else {      // i ≥ 2
           return fib(i−1) + fib(i−2);
         }; // end if
       }; // end if
    }

    Use (the strong form of) mathematical induction to prove that this algorithm correctly computes the nth Fibonacci number if it is given any nonnegative integer n as input.

  2. If a method is called when its precondition is not satisfied then the anticipated behaviour might best be described as “garbage in, garbage out:” virtually nothing about the behaviour of the method can be deduced from its precondition and postcondition.

    In some cases, checking a method’s precondition is too expensive for this to be practical. On the other hand, there are also occasions in which checking of a precondition is simple and efficient, so that it is reasonable to do so.

    One reasonable thing to do — when a precondition is checked and found not to be satisfied — is to throw an exception.

    1. If you are not already familiar with Java’s Exception Class Hierarchy and its uses, please read the Section 2.3 of the textbook You should also take a quick look at the Java tutorials on exceptions; these include additional information that will probably be useful later on.

    2. Consider the recursive algorithm to compute the ith Fibonacci number that was considered above. Identify an appropriate exception (that is already defined as part of Java’s Exception Class Hierarchy) that might reasonably be thrown if a negative integer was supplied as input to a method that implements this algorithm.

  3. Preconditions, postconditions, loop invariants and loop variants, and conditions that are satisfied before particular lines in a program are executed, are all reasonable things to include in documentation of a program.

    1. Read the information about documentation of Java classes and methods that is available on this course’s web site.

    2. Once again, consider the algorithm to compute Fibonacci numbers that is given above.

      Would it be appropriate to document the algorithm’s precondition as part of a javadoc comment? ... and assertion? ...as inline documentation?

    3. Would it be appropriate to list the assertion that “i ≥ 2” (at the beginning of the second, inner else block) as part of a javadoc comment? ... an assertion? ...as inline documentation?

  4. The program Fibonacci1.java includes an implementation of the recursive algorithm to compute Fibonacci numbers that we have been considering. This is called by a main method to compute and print the nth Fibonacci number for integers n between 0 and 40.

    1. Download, compile and run this program. You should find that the resulting output looks like the following.

      Test of a Simple Fibonacci Number Calculator n: 0; nth Fibonacci number: 0 n: 1; nth Fibonacci number: 1 n: 2; nth Fibonacci number: 1 n: 3; nth Fibonacci number: 2 n: 4; nth Fibonacci number: 3 n: 5; nth Fibonacci number: 5 n: 6; nth Fibonacci number: 8 n: 7; nth Fibonacci number: 13 n: 8; nth Fibonacci number: 21 n: 9; nth Fibonacci number: 34 n: 10; nth Fibonacci number: 55 n: 11; nth Fibonacci number: 89 n: 12; nth Fibonacci number: 144 n: 13; nth Fibonacci number: 233 n: 14; nth Fibonacci number: 377 n: 15; nth Fibonacci number: 610 n: 16; nth Fibonacci number: 987 n: 17; nth Fibonacci number: 1597 n: 18; nth Fibonacci number: 2584 n: 19; nth Fibonacci number: 4181 n: 20; nth Fibonacci number: 6765 n: 21; nth Fibonacci number: 10946 n: 22; nth Fibonacci number: 17711 n: 23; nth Fibonacci number: 28657 n: 24; nth Fibonacci number: 46368 n: 25; nth Fibonacci number: 75025 n: 26; nth Fibonacci number: 121393 n: 27; nth Fibonacci number: 196418 n: 28; nth Fibonacci number: 317811 n: 29; nth Fibonacci number: 514229 n: 30; nth Fibonacci number: 832040 n: 31; nth Fibonacci number: 1346269 n: 32; nth Fibonacci number: 2178309 n: 33; nth Fibonacci number: 3524578 n: 34; nth Fibonacci number: 5702887 n: 35; nth Fibonacci number: 9227465 n: 36; nth Fibonacci number: 14930352 n: 37; nth Fibonacci number: 24157817 n: 38; nth Fibonacci number: 39088169 n: 39; nth Fibonacci number: 63245986 n: 40; nth Fibonacci number: 102334155

      You should have noticed something interesting (and potentially problematic) about the time used by this program to compute the larger Fibonacci numbers that are shown above. (If that is not true then you should modify the program so that it computes the next few Fibonacci numbers as well, and then run it again.)

    2. Take some time and make sure that you understand all the Java statements that are included in the above Java program. Section A.5 of Appendix A of the Koffman and Wolfgang reference, for example, includes information about formatting of output that has been used here.

      Note, by the way, that some of the previous questions on this exercise have more than one right answer! Consequently you shouldn’t be disturbed if the documentation or use of an exception in this program is different than you had expected.

    3. Use javadoc to generate an HTML page that documents Fibonacc1.java. You should find that this produces quite a few files, including a file named index.html. When this file is viewed with a web browser you should see something like this.

      Note, by the way, that a precondition and postcondition for the fib method are included in the page generated by javadoc even though there are not javadoc tags for these. You will be expected to include preconditions and postconditions in your own javadoc output (for this course) in the same way.

    4. In order to test your understanding of Java’s exception handling mechanism, write a program called myFib1.java that prompts a user for an integer n and then does one of the following things (depending on the type of input that has been received):

      • If the input is a nonnegative integer n then the method fib included in the given Fibonacci1.java program is called to generate the nth Fibonacci number, and this is displayed as output.

      • If the input is a negative integer then a message is displayed, reminding the user that the input should be greater than or equal to zero.

      • If the input is not an integer at all then a message is displayed to tell the user that the input has the wrong type.

      Your main method should consist of a try block that is only a few lines long that does the work required when the input is a nonnegative integer — and that does not check for any input errors — as well as several catch blocks that are used to produce the required output if the input is negative or not an integer.

      You will be modifying this program later on in this exercise, so it is worthwhile to spend the time needed to write it (and make sure that it works) now.

  5. If you solved the previous problem they you should understand that one — quite serious — problem with our Fibonacci computation algorithm is that it is much too slow. We will overcome this problem by replacing it with a more efficient algorithm.

    1. In order to see how we can improve things, trace the execution of the currently used algorithm by hand in order to compute the fifth Fibonacci number, F5.

      Make note of the other Fibonacci numbers that are being computed along the way — and note the number of times that each of these is recursively generated.

    2. In general, for a nonnegative integer n, the only Fibonacci numbers whose values are generated during a recursive computation of Fn are the Fibonacci numbers Fi for integers i between 0 and n. However, as the previous part of this problem should suggest, each can be computed many, many times.

      Under these circumstances it can be considerably faster to compute the values F0, F1, F2, ..., Fn once each, storing each value in an array when it is first computed and then accessing the array instead of computing these values all over again.

      The program Fibonacci2.java implements an algorithm that uses this strategy.

      Sketch a proof of correctness of the method, fib, that is included in this program. If you have completed the previous exercises then you should be able to use the loop invariant and the loop variant included in the documentation of this method to do this without too much trouble.

    3. Compile and run the Fibonacci2 program. You should find that, except for the identifying line at the beginning, the outputs generated by Fibonacci1 and Fibonacci2 are identical. On the other hand, you should find that Fibonacci2 computes values considerably more quickly.

    4. Notice that Fibonacci2 also includes an implementation of the original Fibonacci number algorithms (now called sfib) and that this is referenced in an assertion that is part of the new method called fib.

      Run the Fibonaacci2 program again, this time with assertion checking enabled. What have you noticed about the running time used by the algorithm? Why has it changed?

    5. Introduce an error in the fib method by setting the value of A[0] to be 1 instead of 0. Compile and run the program again, with assertion checking enabled, in order to see how assertions can be of use when testing programs.

  6. While Fibonacci2 is now reasonably fast it can still be improved.

    1. Trace the execution of Fibonacci2 in order to compute F8. When is the last time that F2 is used? ...F3? ...F4?

    2. If you completed the first part of the problem then you have probably noticed that the ith Fibonacci number, Fi, is never used after the i+2nd Fibnoacci number has been generated. Consequently, Fibonacci2 uses considerably more storage space than is necessary: You never really need to store more than three Fibonacci numbers at once.

      The program Fibonacci3.java computes Fibonacci numbers using storage space more efficiently than previous algorithms. Sketch a proof of correctness of the method fib included in this program; once again, this should not be too hard to do, if you take advantage of the information included in this program’s documentation.

    3. Compile and run the program. You should find that its output is identical to that of Finonacci2, after the first line that describes the purpose of the program.

  7. Unfortunately, there is a serious problem with all the algorithms that we have seen so far.

    1. In order to see that this is the case, modify Fibonacci3.java so that it generates and displays the nth Fibonacci number for each integer n between 0 and 99. If you modify the formatting in second printf statement in order to allow numbers that are up to 22 digits long to be displayed, then this will ensure that every value that can be stored using Java’s long data type will be correctly (and neatly) displayed.

    2. It is easy to prove (using mathematical induction) that Fn+1 ≥ Fn for every integer n ≥ 0.

      With that information in mind, compile and run your modified Fibonacci3 program. What is noticeable about the last ten values that are generated?

    3. If you successfully completed the first two parts of this problem then you will have discovered that at least a few of the values that are being displayed are not Fibonacci numbers at all!

      This is due to the fact that the Fibonacci numbers grow very quickly: For n ≥ 93, the Fibonacci number Fn is too large to be represented using Java’s long data type.

      Unfortunately (due to the degradation in performance that it would require) Java programs do not check for or report numerical overflow — as you have now discovered.

      Fortunately — for this particular problem — it is not very difficult for us to do this ourselves. Suppose that n is the largest integer such that Fn can be represented as a long integer. Then (according to what we know about Fibonacci numbers by now, and the information about Java’s primitive data types found in Section 1.1 of the textbook) it must be the case that

      Fn−1 ≤ Fn ≤ 9,223,372,036,854,775,807 < Fn+1 = Fn + Fn−1.

      Due to numerical overflow, the value that Java will store instead of Fn+1 will be

      Gn+1 = Fn+1 − 2 × 9,223,372,036,854,775,808 = Fn + Fn−1 − 2 × 9,223,372,036,854,775,808.

      Since Fn−1 < 9,223,372,036,854,775,808 (as noted above) it must be the case that Gn+1 < Fn.

      The program Fibonacci4.java uses the above observations to check for numerical overflow during the computation of a Fibonacci number. A “new” exception, NumericalOverflowException, is defined and thrown when numerical overflow has been detected.

      Download, compile and run this program to confirm that it behaves as claimed.

      If the part of the program that provides the NumericalOverflowException exception seems mysterious, don’t worry about it! You will learn more about object-oriented programming later on, and this part of the program should make more sense after that.

    4. Modify your program, MyFib1.java, in order to produce a second program, MyFib2.java, to solve (almost) the same problem: This time, Fibonacci numbers should be computed more efficiently — and an appropriate error message should displayed, rather than reporting an incorrect value, if numerical overflow occurs.

    Note: Please don’t assume that detecting numerical overflow will be this easy in other situations! We took advantage of several properties of the values we were computing — which are unlikely to hold in other situations — in order to develop a fast test for numerical overflow that is reliable for this particular problem.

  8. Fortunately, Java’s long data type represents integers that are large enough for a wide variety of problems to be solved. Unfortunately — as we have now seen — some problems require us to work with larger integers than this data type provides.

    While it is good to know that we can detect and report at least some cases where Java’s long integers are not “large enough,” it would be even better to have support for extended precision computations when these are required. The package java.math provides the support that we need for this.

    1. Review Sun’s documentation of the BigInteger class (which is part of the java.math package).

    2. Download, compile and run the Fibonacci5.java program. This is essentially the same as the “Fibonacci3.java” program, except that the class BigInteger is being using instead of Java’s long data type.

    3. Modify your program, MyFib1.java, once again; the resulting program, MyFib3.java, should be capable of efficiently computing significantly larger Fibonacci numbers than before.

Note: You might have found this exercise to be frustrating: It begins with a claim to show how ideas from class will be applied to Java software development and then illustrates limitations and problems with these techniques!

However, quite a bit of your time and energy in any career in software development is likely to be spent on testing and maintenance of software. We will be considering software testing next; a detailed understanding of software — as a proof of its correctness should provide — can be quite useful when tests are being designed and when software is being debugged.

Note: When we replaced an inefficient recursive algorithm with a much more efficient one that stored values in a data structure and looked them up, instead of computing them over again, we were using a technique for the design of algorithms called dynamic programming. You benefit from this technique on a regular basis, because it has also been used to develop efficient algorithms to compile computer programs. Computer Science students will study this algorithm design technique when they take CPSC 413.


Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/F10/tutorials/self-study2.html