CSC152 2005F, Class 29: Algorithm Analysis (1) Admin: * Exams not graded yet. Sorry. Hopefully tomorrow. * Challenge for tomorrow: Rewrite the recursive exponentiation with a while loop * Hint 1: Use the rule that x^(2k) = (x^2)^k * Hint 2: When doing tail recursion, we almost always introduce an accumulator. You also often need one when converting recursive functions to while loops. * Hint 3: You may want to try tail recursion first Overview: * A motivating example: Exponentiation * Standard mechanism * Elegrant recursion * Pre-computer strategy * Comparing algorithms * Ignoring details Problem: Compute x^n for non-negative integer n and BigDecimal x BigDecimal result = new BigDecimal(1.0); for (int i = 0; i < n ; i++) { result = result.multiply(x); } Observation: x^(2k) = (x^k)^2 public BigDecimal expt(BigDecimal x, int n) { // Base case: x^0 = 1 if (n is 0) { return new BigDecimal(1.0); } // Recursive x^(2k) = (x^k)*(x^k) ; k = n/2 else if (n is even) { BigDecimal tmp = expt(x, n/2); return tmp.multiply(tmp); } // Recursive: x^n = x^(n-1)*x else { return x.multiply(expt(x,n-1)); } } // expt(BigDecimal, int) Which of the two versions of expt do you prefer? Why? * First: 7 * Conceptually simple * Short code * Second: 1 * Might be faster: Seems to do fewer computations * We certainly do fewer multiplications; does multiplication depend on the size of the number? * Informal tests show that the second is correct, in spite of you naysayers * Careful analysis should also suggest that is correct Consider 3^32 For loop: 32 multiplications Recursive: * 1 division to get 16 1 multiplication of 3^16 * 3^16 * 1 division to get 8 1 multiplication of 3^8 * 3^8 * 1 division to get 4 1 multiplciation of 3^4 * 3^4 * 1 division to get 2 1 multiplciation of 3^2 * 3^2 * 1 division to get 1 1 multiplication of 3^1 * 3^1 * 1 subtraction to get 0 1 multiplication of 3^0 * 3 * 6 multiplcations, 5 divisions; 1 subtraction * If we double the exponent, we add only one mult. and division in the recursive case Even though the second is more code, it is likely to be significantly faster Experimentation --- How do you compute 5^20 without a computer? * Run algorithm a or b by hand