10

I have to write a power method in Java. It receives two ints and it doesn't matter if they are positive or negative numbers. It should have complexity of O(logN). It also must use recursion. My current code gets two numbers but the result I keep outputting is zero, and I can't figure out why.

import java.util.Scanner;

public class Powers {

    public static void main(String[] args) {
        float a;
        float n;
        float res;

        Scanner in = new Scanner(System.in);
        System.out.print("Enter int a ");
        a = in.nextFloat();

        System.out.print("Enter int n ");
        n = in.nextFloat();

        res = powers.pow(a, n);

        System.out.print(res);
    }

    public static float pow(float a, float n) {
        float result = 0;

        if (n == 0) {
            return 1;
        } else if (n < 0) {
            result = result * pow(a, n + 1);
        } else if (n > 0) {
            result = result * pow(a, n - 1);
        }

        return result;
    }
}
Eran
  • 387,369
  • 54
  • 702
  • 768
dEv93
  • 163
  • 1
  • 3
  • 11
  • whenever you only need to add somethings initialize sum=0, but when you want to multiply and add intialize sum=1 – Vihar Nov 01 '14 at 13:54
  • Why are you using `float` when you were told to use `int`? More importantly - not only is your use of `result` wrong (because of the zero), the complexity of your function is O(n), not O(log n). You have to reduce the problem to at least a half of its size in the recursion to get O(log n). – RealSkeptic Nov 01 '14 at 13:56
  • 1
    That's `O(n)` complexity even though it's recursive. A `O(logn)` algorithm would always divide the power(`n` in this case) by 2, not decreasing by 1. – Daniel Nov 01 '14 at 14:04
  • so yeah i fixed that problem i had of result being multiplied. Now i have ....result = a * pow(a,n+1) and result = a * pow(a,n-1). I am getting the correct values for positive numbers but i am not getting the correct value when i plug in a negative number. – dEv93 Nov 01 '14 at 14:05
  • But why the hell to you ask for int and make computations in float ??? What happens if you get 2.5 answer for `n` ? Doesn't it look like an infinite recursion ? – Serge Ballesta Nov 01 '14 at 14:19

9 Answers9

44

Let's start with some math facts:

  • For a positive n, aⁿ = a⨯a⨯…⨯a n times
  • For a negative n, aⁿ = ⅟a⁻ⁿ = ⅟(a⨯a⨯…⨯a). This means a cannot be zero.
  • For n = 0, aⁿ = 1, even if a is zero or negative.

So let's start from the positive n case, and work from there.

Since we want our solution to be recursive, we have to find a way to define aⁿ based on a smaller n, and work from there. The usual way people think of recursion is to try to find a solution for n-1, and work from there.

And indeed, since it's mathematically true that aⁿ = a⨯(aⁿ⁻¹), the naive approach would be very similar to what you created:

public static int pow( int a, int n) {
    if ( n == 0 ) {
        return 1;
    }
    return ( a * pow(a,n-1));
}

However, the complexity of this is O(n). Why? Because For n=0 it doesn't do any multiplications. For n=1, it does one multiplication. For n=2, it calls pow(a,1) which we know is one multiplication, and multiplies it once, so we have two multiplications. There is one multiplication in every recursion step, and there are n steps. So It's O(n).

In order to make this O(log n), we need every step to be applied to a fraction of n rather than just n-1. Here again, there is a math fact that can help us: an₁+n₂ = an₁⨯an₂.

This means that we can calculate aⁿ as an/2⨯an/2.

But what happens if n is odd? something like a⁹ will be a4.5⨯a4.5. But we are talking about integer powers here. Handling fractions is a whole different thing. Luckily, we can just formulate that as a⨯a⁴⨯a⁴.

So, for an even number use an/2⨯an/2, and for an odd number, use a⨯ an/2⨯an/2 (integer division, giving us 9/2 = 4).

public static int pow( int a, int n) {
    if ( n == 0 ) {
        return 1;
    }
    if ( n % 2 == 1 ) {
        // Odd n
        return a * pow( a, n/2 ) * pow(a, n/2 );
    } else {
        // Even n
        return pow( a, n/2 ) * pow( a, n/2 );
    }
}

This actually gives us the right results (for a positive n, that is). But in fact, the complexity here is, again, O(n) rather than O(log n). Why? Because we're calculating the powers twice. Meaning that we actually call it 4 times at the next level, 8 times at the next level, and so on. The number of recursion steps is exponential, so this cancels out with the supposed saving that we did by dividing n by two.

But in fact, only a small correction is needed:

public static int pow( int a, int n) {
    if ( n == 0 ) {
        return 1;
    }
    int powerOfHalfN = pow( a, n/2 );
    if ( n % 2 == 1 ) {
        // Odd n
        return a * powerOfHalfN * powerOfHalfN;
    } else {
        // Even n
        return powerOfHalfN * powerOfHalfN;
    }
}

In this version, we are calling the recursion only once. So we get from, say, a power of 64, very quickly through 32, 16, 8, 4, 2, 1 and done. Only one or two multiplications at each step, and there are only six steps. This is O(log n).

The conclusion from all this is:

  1. To get an O(log n), we need recursion that works on a fraction of n at each step rather than just n - 1 or n - anything.
  2. But the fraction is only part of the story. We need to be careful not to call the recursion more than once, because using several recursive calls in one step creates exponential complexity that cancels out with using a fraction of n.

Finally, we are ready to take care of the negative numbers. We simply have to get the reciprocal ⅟a⁻ⁿ. There are two important things to notice:

  • Don't allow division by zero. That is, if you got a=0, you should not perform the calculation. In Java, we throw an exception in such a case. The most appropriate ready-made exception is IllegalArgumentException. It's a RuntimeException, so you don't need to add a throws clause to your method. It would be good if you either caught it or prevented such a situation from happening, in your main method when you read in the arguments.
  • You can't return an integer anymore (in fact, we should have used long, because we run into integer overflow for pretty low powers with int) - because the result may be fractional.

So we define the method so that it returns double. Which means we also have to fix the type of powerOfHalfN. And here is the result:

public static double pow(int a, int n) {
    if (n == 0) {
        return 1.0;
    }
    if (n < 0) {
        // Negative power.
        if (a == 0) {
            throw new IllegalArgumentException(
                    "It's impossible to raise 0 to the power of a negative number");
        }
        return 1 / pow(a, -n);
    } else {
        // Positive power

        double powerOfHalfN = pow(a, n / 2);
        if (n % 2 == 1) {
            // Odd n
            return a * powerOfHalfN * powerOfHalfN;
        } else {
            // Even n
            return powerOfHalfN * powerOfHalfN;
        }
    }
}

Note that the part that handles a negative n is only used in the top level of the recursion. Once we call pow() recursively, it's always with positive numbers and the sign doesn't change until it reaches 0.

That should be an adequate solution to your exercise. However, personally I don't like the if there at the end, so here is another version. Can you tell why this is doing the same?

public static double pow(int a, int n) {
    if (n == 0) {
        return 1.0;
    }
    if (n < 0) {
        // Negative power.
        if (a == 0) {
            throw new IllegalArgumentException(
                    "It's impossible to raise 0 to the power of a negative number");
        }
        return 1 / pow(a, -n);
    } else {
        // Positive power
        double powerOfHalfN = pow(a, n / 2);
        double[] factor = { 1, a };
        return factor[n % 2] * powerOfHalfN * powerOfHalfN;
    }
}
RealSkeptic
  • 33,993
  • 7
  • 53
  • 79
  • this was a great explanation. thank you. I was getting close and this explained very the negative numbers part. – dEv93 Nov 01 '14 at 18:37
  • great explanation! – Preetam May 02 '17 at 11:31
  • as you have declared an array {1, a} with position 0 & 1. So the mod oprator is selecting 0 or 1 position of the array based on even or odd of n number. but I would like to improve a little bit instead of **factor[n % 2]** i would to like to check even or odd by binary comparison **factor[n&1]** – Chowdhury Md Rajib Sarwar Jun 07 '22 at 06:53
1

pay attention to :

float result = 0;

and

result = result * pow( a, n+1);

That's why you got a zero result. And instead it's suggested to work like this:

result = a * pow( a, n+1);
Chiron
  • 974
  • 1
  • 8
  • 20
1

Beside the error of initializing result to 0, there are some other issues :

  1. Your calculation for negative n is wrong. Remember that a^n == 1/(a^(-n)).
  2. If n is not integer, the calculation is much more complicated and you don't support it. I won't be surprised if you are not required to support it.
  3. In order to achieve O(log n) performance, you should use a divide and conquer strategy. i.e. a^n == a^(n/2)*a^(n/2).
Eran
  • 387,369
  • 54
  • 702
  • 768
  • we were told that out program should be able to do pow(2,-2) and that should give .25 ... your saying that for O(logN) i should take the N and divide by 2? for either case of n – dEv93 Nov 01 '14 at 14:34
  • @Yaboy93 For pow(2,-2), you should compute pow(2,2) and then return 1/pow(2,2). As for dividing by two, you should take care. First of all, change n to int. Then, if n is even you make a recursive call of pow(a,n/2) and multiply it by itself. If n is odd, you multiply pow(a,n/2) by pow(a,n/2+1). For example, pow(2,7)==pow(2,3)*pow(2,4). – Eran Nov 01 '14 at 14:44
1

Here is a much less confusing way of doing it, at least if your not worred about the extra multiplications. :

public static double pow(int base,int exponent) {
        if (exponent == 0) {
            return 1;
        }
        if (exponent < 0) {
            return 1 / pow(base, -exponent);
        }
        else {
            double results = base * pow(base, exponent - 1);
            return results;
        }
    }
Jameson
  • 11
  • 2
1
# a pow n = a pow n%2 * square(a) pow(n//2)
# a pow -n = (1/a) pow n
from math import inf
def powofn(a, n):
    if n == 0:
        return 1
    elif n == 1:
        return a
    elif n < 0:
        if a == 0 : return inf
        return powofn(1/a, -n)
    else:
        return powofn(a, n%2) * powofn(a*a, n//2)
0

A good rule is to get away from the keyboard until the algorythm is ready. What you did is obviously O(n).

As Eran suggested, to get a O(log(n)) complexity, you have to divide n by 2 at each iteration.

End conditions :

  • n == 0 => 1
  • n == 1 => a

Special case :

  • n < 0 => 1. / pow(a, -n) // note the 1. to get a double ...

Normal case :

  • m = n /2
  • result = pow(a, n)
  • result = resul * resul // avoid to compute twice
  • if n is odd (n % 2 != 0) => resul *= a

This algorythm is in O(log(n)) - It's up to you to write correct java code from it

But as you were told : n must be integer (negative of positive ok, but integer)

Serge Ballesta
  • 143,923
  • 11
  • 122
  • 252
0
import java.io.*;
import java.util.*;
public class CandidateCode {
    public static void main(String args[] ) throws Exception {

    Scanner sc = new Scanner(System.in);
    int m = sc.nextInt();
    int n = sc. nextInt();
     int result = power(m,n);
     System.out.println(result);
    }
     public static int power(int m, int n){
         if(n!=0)
            return (m*power(m,n-1));
        else 
            return 1;
     }

}
0

try this:

    public int powerN(int base, int n) {return n == 0 ? 1 : (n == 1 ? base : base*(powerN(base,n-1)));
Morriss
  • 39
  • 6
-1

ohk i read solutions of others posted her but let me clear you those answers have given you the correct & optimised solution but your solution can also works by replacing float result=0 to float result =1.

  • That will not make it work correctly; that will just make it always return `1`. @Chiron's answer already explains how to fix it. – Erwin Bolwidt Aug 09 '20 at 05:26