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?

• kelalaka: Hint: $a^{2n} = a^{n} a^{n}$ and $a^{2n+1} = a^{n} a^{n} a$

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.