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