<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">/** demo of recursive function Power.
    This class has 4 methods that compute v**p, where p &gt;= 0.
    
    power1 takes time proportional to p --in fact, it makes p+1 calls in total.
    
    power2 takes time proportional to the logarithm of p, making use
           of the fact that v**p = (v*v) ** (p/2) for even p.
           This is a GREAT savings! If p is 2**15, i.e. 32768, it takes
           about 16 recursive calls and not 32768!
           This makes a huge difference. In fact, power1 will not even
           compute in this case because the number of stack frames needed
           is too large.
           
    power3 is a version of power1 that returns not only the answer but
           also the number of calls it took to compute the answer. To
           do this, power3 makes use of a class (given at the end of this
           file) whose only purpose is to aggregate or collect two values into
           one object, so that the function can return both. This shows how
           simple it is to have function that returns more than one value in
           OO programming.
           
    power4 is a version of power3 that returns not only the answer but also
    the number of calls it took to compute the answer.
    
    After studying the simple methods power1 and power2,
    We suggest you try these two calls:
    Power.power1(2,15)
    Power.power2(2,15)
    Power.power3(.1, 32768)   --what happens?
    Power.power4(.1, 32768)
    */
public class Power {
    
    /** The argument should be an array of size at least 2. 
      arg[0] and arg1[1] should be strings containing ints, used
      as parameters to calls on power1 and power2 */
    public static void main(String[] args) {
        int val = Integer.parseInt(args[0]);
        int pow = Integer.parseInt(args[1]);
        System.out.println(power1(val, pow));
        System.out.println(power2(val, pow));
    }
    
    /** Return x**p (x multiplied by itself p times).
      Precondition: p &gt;= 0. */
    public static double power1(double v, int p) {
        //Note: this version takes time proportional to exponent p
        if (p == 0)
            return 1;
        
        return v * power1(v, p - 1);
    }
    
    /** Return x**p (x multiplied by itself p times).
      Precondition: p &gt;= 0. */
    public static double power2(double v, int p) {
        //Note: this version takes time proportional to the logarithm
        // (to the base 2) of p.
        // Example. If p = 32768, which is 2**15, it takes only
        // about 15 recursive calls!
        if (p == 0)
            return 1;
        
        if (p % 2 == 1)
            return v * power2(v, p-1);  // recursive call if p is odd
        
        // use the fact that for even p, v**p = (v*v)**(p/2)
        // example:  2*2*2*2*2*2*2*2 = 2**8 or (2*2)**4
        return power2(v*v, p/2);
    }
    
    /** Return the pair 
      x**p (x multiplied by itself p times)
      the number of calls on power3, including this one
      Precondition: p &gt;= 0. */
    public static DoubleInt power3(double v, int p) {
        //Note: this version takes time proportional to exponent p
        if (p == 0)
            return new DoubleInt(1, 1);
        
        DoubleInt ans= power3(v, p - 1);
        return new DoubleInt(v * ans.d, ans.i + 1);
    }
    
    /** Return x**p (x multiplied by itself p times).
        Precondition: p &gt;= 0. */
    public static DoubleInt power4(double v, int p) {
        // Note: this version takes time proportional to the logarithm
        // (to the base 2) of p.
        // Call it with ppower4(.1, 32768) and see how many calls it makes
        if (p == 0)
            return new DoubleInt(1, 1);
        
        if (p % 2 == 1) {
            DoubleInt ans= power4(v, p - 1);
            return new DoubleInt(v * ans.d, ans.i + 1);  // recursive call if p is odd
        }
        
        // use the fact that for even p, v**p = (v*v)**(p/2)
        // example:  2*2*2*2*2*2*2*2 = 2**8 or (2*2)**4
        DoubleInt ans= power4(v*v, p/2);
        return new DoubleInt(v * ans.d, ans.i + 1);
    }
    
} 

/** An instance is a (double, int) pair.
  This class is used ONLY to be able to aggregate two
  values so that power3 and power4 can return two values:
  The double value of v**p and the number of calls it took
  to calculate it. For this reason, we make the fields public
  and don't write getter/setters. */
class DoubleInt {
    public double d; // value of call
    public int i;    // number of calls needed
    
    /** Constructor: an instance with double value d and int value i */
    public DoubleInt(double d, int i) {
        this.d= d;
        this.i= i;
    }
    
    /** return representation of this pair */
    public @Override String toString() {
        return "value: " + d + ", number of calls: " + i;
    }
    
}


</pre></body></html>