In this lab, you will explore the running time of recursive and looping algorithms
to compute the same functions and implement a StopWatch class to
facilitate similar time studies in the future. More specifically, we are interested
in the Fibonacci numbers and the Collatz function, both discussed in lecture.
Each of the two “functions” of interest is also sometimes thought of in terms of a sequence: here for Fibonacci we mean a function that returns the value of its own calls for the two arguments just less than its own (all values are integers here unless otherwise specified), but returning 0 and 1 for those arguments, respectively. For the Collatz function, we mean a function that returns the number of calls required for the usual recursive algorithm to reach a result of 1; the algorithm returns 1 for argument 1 and otherwise either calls recursively for one half the argument (if the original argument is even) or for three times the argument plus one (if it is odd). In particular, the Collatz function we are looking for should also return 1 for an argument of 1, since we make just the one call before terminating. (We might call this the “counting Collatz” function in order to distinguish it from the usual one that is at the core of the process).
Regarding the algorithms that you will test, the idea is to compare the timings of recursive versions with looping versions. You can easily write recursive versions according to the instructions above; what about looping versions? For Fibonacci, the obvious idea is to keep two integer variables, representing the values of the “lower-numbered” calls, and to “shift the values down” by copying the higher one into the lower one and the sum into the higher one. For the Collatz function, you can simply modify a current argument value to be the next result and continue until you reach a value of 1.
Note that in all cases, the result of the recursive versus looping algorithms should be the same (for the same arguments); i.e., the same functions should be computed, just in different ways.
As mentioned above, you will also implement a StopWatch class in order
to facilitate timing. The idea is that a new instance of this class can be created,
started, and then queried for the current time passed since started. We could also
allow it to be stopped, but there will really be no need, although you should allow
it to be re-set to “zero”. When a StopWatch object is
first run, it takes note of (stores in a variable) the current system time; when it
is inspected, it should subtract the stored time from the current time and report it
back. When it is re-set, it should store a new current time. System time information
from System.nanoTime().
Remember to start or re-set a StopWatch before you start to compute the
value of one of the target functions; not at each call, but from the outside, before
the first call and after the final result, so that you get a clean value for the
whole computation.
In all, you should implement three classes:
StopWatch class, with instance methods as above (in other words,
you should expect to create new multiple StopWatch objects over
time, if needed).
Algorithms class, with various different algorithms, implemented
as static methods, corresponding to the various combinations of which function is
computed (Fibonacci or Collatz), and how it is computed (recursive or looping
version), and possibly whether it reports on intermediate values (see below).
main method that creates a
StopWatch instance or instances and calls the Algorithms
methods in some appropriate way, printing out results. You should implement an
outer loop which allows a user to input requests for comparisons based on ranges of
values, printing a table of function and timing results. For example, you might
ask for Fibonacci or Collatz, then a range of input values (the user might reply
asking for inputs from 10 to 20), then print a table with columns including the
argument value (i.e., 10 to 20), the results and timing for the recursive version
of the algorithm and the results and timing for the looping version (that’s
five columns in all). You may wish to use Java’s printf
capabilities to format your output nicely in a table.
As a variation, you might want to try implementing versions of some of the algorithms that print out intermediate results; you'll probably find that the printing itself takes up considerable time compared to the basic integer computations. If you do this, you might want to store the timing results in an array and print them at the end of an entire run, in order to avoid interfering with the output of the intermediate values.