0
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Hint: $a^{2n} = a^{n} a^{n}$ and $a^{2n+1} = a^{n} a^{n} a$ $\endgroup$ – kelalaka Jan 1 at 21:37
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.