Outline of Class 27: Efficiency, continued

Miscellaneous

• Since ownership of software was discussed in class, I've talked to a few people about it. I've been told that Grinnell generally gives students rights to the software they create, but does require a formal review process first.
• Someone volunteered for another case study, but I've forgotten who. Please send me email.
• An exercise for those interested in applying for the student programmer job will be available next week.
• I'll warn you that none of our optimizations may be particularly important; a quick test on my machine suggested that 1.03^10,000 was quick, even with the dumb exponention. Nonetheless, it's a good exercise.
• Mr. Stone may visit this class later this week.
• We may have a photographer in class today.

The Present-Value Problem, Revisited

• Recall that we've been trying to optimize a Java-based solution to the "find the present value of an investment of I dollars for Y years at an annual rate of R compounded annually ".
• Many of our solutions involved the computation of (1+R)^Y. For learning purposes, we wrote our own exponentiation function.
• Another good solution involved the use of tables. We may want to think about that one in more detail.

Optimizing exp()

• We've seen that it is possible to go from an O(n) version of exp() to an O(logn) version. However, the new version is recursive but not tail recursive. Can we make it tail-recursive (that is, it does nothing after a recursive call)? Can we make it iterative? Can we do both without using a separate stack?

A Tail-Recursive exp()

• To make exp() tail recusive, we'll need to do a few differnt things.
• We'll add an accumulator (which is a standard technique in making functions tail-recursive). We'll use it to accumulate the multiplications from the odd exponents.
• We'll use a trick for the even exponents. In particular, we'll observe that x^(2k) is (x^2)^k.
• The pre- and post-conditions can be found in the previous version.

  public static double exp(double x, int n) {
    return exp(x,n,1.0);
  } // exp
  public static double exp(double x, int n, double acc) {
    if (n == 0) return acc;
    if (even(n)) return exp(x*x, n/2, acc);
    else return exp(x, n-1, x*acc);
  } // exp
  

An Efficient Iterative exp()

• Since not all languages efficiently implement tail recursion, we may need to make our tail-recuirsvie exp() iterative.
• How do we do this? More or less the same way that a compiler will.

  public static double exp(double x, int n) {
    double acc = 1.0;
    while (n > 0) {
      if (even(n)) {
        x = x*x;
        n = n / 2; // or n >> 1
      }
      else {
        acc *= x;
        n = n - 1;
      }
    } // while
    return acc;
  } // exp
  

In-Class Exercise

• Let's try the various improvements. Each computer in the first eight rows will implement an appropriate form of the presentValue function in Java. Each computer in the last eight rows will do the same thing, but in a language other than Java.
  • galton and robinson: original iterative version using doubles
  • herstein and stokes: original iterative version using ints
  • jordan and taylor: separate call to iterative exp() function (using doubles)
  • klein and venn: recursive O(logn) exp() function (using doubles)
  • lie and wyel: tail-recursive O(logn) exp() (using doubles)
  • markov and wronski: iterative O(logn) exp() (using doubles)
  • neyman and young: iterative O(logn) exp() (using ints)
  • peano and zorn: precompute a table of present values for 3% after one to ten years (inclusive) and use that table.
• Compute the present value of $5 at an annual interest rate of 3% for 0, 1, 10, 100, 1000, and 10,000 years. Time each, if possible.
  • If your program is still too quick, try doing the computation many times (put it in a loop).
• Report results, programmer time (to implement), and system time.
• The Java programmers can use a template for the rest of their Java code, so that all they need to do is fill-in and modify certain parts.
• If you still have time, try generating some reasonable empty or near-empty programs so that we can avoid considering Java's excessive startup time.