CSC152 2005F, Class 27: Parameterized Classes, Part 1: The Motivating Problem

Admin
* I may be a few minutes late.  Start looking at Mathematician.java
  (particularly at exp2) and at IntegerVariable.java.

Overview
* A new problem: Exponentiation

Background:
* I've created a class called "IntegerVariable"
  * Like Integer, but you can change 'em.
  * One idea: the decrement method might take different kinds of parameters (ints, IntegerVariables, Integers); we write one for each: Overloading
    * Contrast with polymorphism, in which you write one method that accepts a variety of types of parameters

Let's write the following:
  // pre: n>=0
  public static IntegerVariable expt3(IntegerVariable x, int n)
  // Multiply x by itself and subtract one each time until "n runs out"
  // Recursive solution
  // Base case:
  if (n == 0) 
  {
    // x^0 = 1
    return new IntegerVariable(1);
  }
  else 
  {
    return x.multiply(expt3(x,n-1));
  }

compute 2 to the third (note that sam is not going to write IntegerVariable)

expt3(2,3)
  return 2.multiply(expt3(2,2))
    need to compute expt3(2,2)
    return 2.multiply(expt3(2,1))
      need to compute expt(2,1)
        return 2.multiply(expt(2,0))
	  need to compute expt(2,0)
	  return 1
	2*1 = 2
    2*2 = 4
  2*4 = 8

Most computer scientists, who are less well trained than you,
would use a loop.

A more efficient strategy:
* Observation: x^(2n) = x^n * x^n
* Rephrase: x^n = x^(n/2) * x^(n/2) for even n
* As code:
  if (even(n)) {
    IntegerVariable tmp = expt2(x,n/2);
    return tmp.multiply(tmp);
  }
  else {
    return x.multiply(expt2(x,n-1));
  }
* Is this better?  Suppose we had to compute x^100.  How many multiplications do we do?
  * Using original: ~100
  * Using loop: ~100
  * Using new strategy:
    1 (multiplying x^50 * x^50)
    1 (multiplying x^25 * x^25)
    1 (multiplying x * x^24)
    1 (multiplying x^12 * x^12)
    1 (multiplying x^6 * x^6)
    1 (multiplying x^3 * x^3)
    1 (multiplygin x * x^2)
    1 (multiplying x * x)
    1 (multiplying x * 1)

Whoops!  2^100 is not representable
What do we do?
* Use BigIntegers
* Use preconditions: (x^n <= Integer.MAX_VALUE)
* Throw an exception
  * Left as an optional exercise

* Let's look at the use of BigIntegers
* Create BigIntegerVariable

When you find yourself cutting and pasting code, try to use
polymorphism:
* Create an interface that explains the commonality of the types you want to apply the method to
  * Our interface specifies that it must provide a multiply method
* Make each class implement the interface
  * If we're lucky, "implements NameOfInterface"
  * If we're unlucky, must do more
* Rewrite the method to expect the interface rather than whichever class we started with.