Fast and slow exponentiation

Exercise 1.23

Analyze the cost of the following recursive functions.

They all compute x^n for n \in \mathbb N in different ways.

double power_1 (double x, int n) { 
    if (n == 0){
        return 1;
    } 
    else {
        return x*power_1(x, n - 1); 
    }
}

double power_2 (double x, int n) { 
    if (n == 0){
        return 1;
    } else if (n % 2 == 0) {
        int y = power_2(x, n/2);
        return y*y;
    } else {
        int y = power_2(x, n/2);
        return y*y*x; 
    }
}

double power_3 (double x, int n) {
    if (n == 0){
        return 1;
    } else if (n % 2 == 0) {
        return power_3(x, n/2) * power_3(x, n/2); 
    } else {
     return power_3(x, n/2) * power_3(x, n/2) * x; 
    }
}

After class

Try to solve the following series of Jutge problems in the section Divide-and-Conquer before the next lab. They are all about efficient exponentiation (in one way or another).

• P29212 Modular exponentiation
• P61833 Powers of a matrix
• P74219 Fibonacci numbers (2)
• X39049 Powers of permutations

Using what we discussed in class, what is a good code to use as a starting point to solve the exercises above? (The exercises are listed in increasing order of difficulty.)