Divide and Conquer Algorithm to calculate $a^n$

Question

I am attempting to create an algorithm which given the value of $a \in \mathbb{R}$ and $b \in \mathbb{N}$, calculate $a^n$.

So for example, using the Java language pattern, the algorithm will be defined as follows:

public double exp(float a, int n) {
    ...
}

But I am unable to determine what would be possible sub-problems of this problem as there is not set from which I can create subsets.

How can I achieve this using a divide and conquer method?

Answer 1

I think you are looking for something along these lines.

public double exp(float a, int n) {
    if(n<=0) return 1; // just for safety saying <= instead of == to allow
    if(n==1) return a;
    float floor_exp = exp(a,floor(n/2))
    if(floor(n/2) < ceil(n/2)){
        return floor_exp * floor_exp * a;
    }
    else{
        return floor_exp * floor_exp;
    }
}

Note that floor and ceil are not functions in Java but in Python. Use these for Java. Also this will only work for n >= 0. The result is incorrect for the other case.