# Divide and Conquer Algorithm to calculate $a^n$

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?

• Hint: $a^{2n} = a^{n} a^{n}$ and $a^{2n+1} = a^{n} a^{n} a$ – kelalaka Jan 1 '19 at 21:37

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.