Power function using recursion

Question

I need to write a power method in Java. It gets two ints and it doesn't matter if they are positive or negative numbers. It must have O(logN) complexity. It should also use recursion. My current code gets two numbers, but the result that I continue to output is zero, and I can not understand 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; } } 

Answer 1

Let's start with some mathematical facts:

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

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

Since we want our solution to be recursive, we must find a way to determine aⁿ based on smaller n and work from there. Usually people think of recursion - try to find a solution for n-1 and work from there.

And indeed, since it is mathematically true that aⁿ = a⨯ (aⁿ⁻¹), the naive approach will 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). What for? Since for n = 0 it does not perform any multiplications. For n = 1, it is one multiplication. For n = 2, he calls pow (a, 1), which, as we know, is one multiplication and multiplies it once, so we have two multiplications. At each stage of the recursion, there is one multiplication, and there are n steps. So It O (n).

To do this O (log n), we need every step that needs to be applied to the fraction of n, and not just to n-1. Here again, there is a mathematical fact that can help us: a ^{n₁ + n₂} = a ^n₁ ⨯a ^n₂ .

This means that we can calculate aⁿ as ^{n / 2} ⨯a ^{n / 2} .

But what happens if n is odd? something like a⁹ will be ^4.5 ⨯a ^4.5 . But here we are talking about whole forces. Processing fractions is a completely different matter. Fortunately, we can simply state it as a⨯a⁴⨯a⁴.

So, for an even number, use a ^{n / 2} ⨯a ^{n / 2} and for an odd number use a⨯ a ^{n / 2} ⨯a ^{n / 2} (integer division giving 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 correct results (for positive n, that is). But actually the difficulty here is, again, O (n), not O (log n). What for? Because we calculate powers twice. This means that we actually call it 4 times at the next level, 8 times at the next level, etc. The number of recursion steps is exponential, so this is canceled with the preservation we made by dividing n by two.

But actually only a small correction is required:

 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 call recursion only once. Thus, we get, say, a power of 64, very quickly through 32, 16, 8, 4, 2, 1 and do it. Only one or two multiplications at each step, and there are only six steps. This is O (log n).

The conclusion from all of this:

• To get O (log n), we need a recursion that works for the fraction of n at each step, and not just for n - 1 or n - whatever.
• But a fraction is only part of the story. We need to be careful not to call recursion more than once, since using multiple recursive calls in one step creates exponential complexity that overrides the use of part n.

Finally, we are ready to take care of negative numbers. We just need to get a response ⅟a . There are two important things to notice:

• Do not divide by zero. That is, if you got a = 0, you should not perform the calculation. In Java, we throw an exception in this case. The most suitable prepared exception is an IllegalArgumentException. This is a RuntimeException exception, so you do not need to add a throws to your method. It would be nice if you either caught it or didn’t allow such a situation in your main method when you read in the arguments.
• You can no longer return an integer (in fact, we should use long , because we run an integer overflow for fairly low powers with int ) - because the result can be fractional.

So, we define the method so that it returns twice. This means that we must also fix the type 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 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 handling negative n is only used at the top level of recursion. As soon as we recursively call pow() , it is always with positive numbers, and the sign does not change until it reaches 0.

This should be an adequate solution for your exercise. However, I personally do not like if there at the end, so here is another version. Can you explain why this does 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 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; } } 

Answer 2

pay attention to:

 float result = 0; 

and

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

That is why you got a null result. And instead, he suggested working as follows:

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

Answer 3

In addition to the error initializing result to 0, other problems arise:

• Your calculation of negative n incorrect. Remember that a^n == 1/(a^(-n)) .
• If n is not an integer, the calculation is much more complicated and you do not support it. I won’t be surprised if you don’t have to support him.
• To achieve O(log n) performance, you must use a separation and conquest strategy. those. a^n == a^(n/2)*a^(n/2) .

Answer 4

A good rule is to leave the keyboard until the algorithm is ready. What you did is obviously O (n).

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

Final conditions:

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

Special occasion:

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

The usual case:

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

This algorithm is in O (log (n)). It is up to you to write the correct Java code from it.

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

Answer 5

Here's a much less confusing way to do this, at least if you're not worried about 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; } }