CODEWITHSUNDEEP
javaperformancerecursion
javardee
javardee

Reputation: 55

Power function in Java using recursion

I'm trying to complete an assignment for my Java class where we are to create an efficient method for solving powers (taking a base to an exponent, defined by user's input).

I have just about everything in place, but the efficient method pow2 isn't handling odd exponents correctly. It multiplies the base by one more than it's supposed to. What am I missing here?

For instance, if I input 4 as my base and 5 as my exp, the program will spit out 4096 instead of 1024.

import java.util.Scanner;

public class MyPow {


    public static int countGbl = 0;


    public static double raise(double base, int exp) {

        double b = base;

        for (int i = 1; i < exp; i++){
            countGbl += 1;
            base = base * b;
        }

        return base;
    }


    public static double pow1(double base, int exp) {

        if (base == 0.0) return Double.POSITIVE_INFINITY;
        else if (base == 0.0 && exp >= 0) return 0.0;
        else if (exp == 1) return base;
        else if (base > 0 && exp == 0) return 1.0;
        else{
            if (exp < 0){
                base = 1.0/base;
                exp = -exp;
            }

            if (exp % 2 == 0){
                countGbl++;
                return pow1(base, exp/2) * pow1(base, exp/2);
            }
            else {
                countGbl += 2;
                return pow1(base, exp/2) * pow1(base, exp/2) * base;
            }
        }
    }


    public static double pow2(double base, int exp) {
        double temp = raise(base, exp/2);
        double retval = temp*temp;
        if (exp % 2 == 1){
            countGbl++;
            retval *= temp;
        }
        return retval;
        }





    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);

        System.out.println("Enter base: ");
        double base = Integer.parseInt(s.nextLine());
        System.out.println("Enter exp: ");
        int exp = Integer.parseInt(s.nextLine());

        System.out.println(pow2(base, exp));
        System.out.println(countGbl);

    }
}

Just an FYI, the reason for the pow1 method is because we are to write an example method that isn't as efficient as pow2.

Also, please ignore countGbl. Our professor wants us to count the number of multiplications done during the method calls.

Upvotes: 1

Views: 767

Answers (2)

Roberto Trani
Roberto Trani

Reputation: 1227

I sketched this recursive solution to your problem, where odds and even exponents are treated directly into raise:

public static double raise(double base, int exp) {
    if (exp == 0) {
        return 1;
    } if ((exp % 2) == 1) {

        countGbl += 1;
        return raise(base, exp-1) * base;
    } else {
        double tmp = raise(base, exp/2);

        countGbl += 1;
        return tmp * tmp;
    }
}

public static double pow2(double base, int exp) {
    return raise(base, exp);
}

Here the number of multiplications is logarithmic with respect to exp.

Upvotes: 1

rgettman
rgettman

Reputation: 178253

It looks like you are attempting to make the optimization:

baseexp = baseexp/2 * baseexp/2 * base

where exp is odd, and where exp/2 is Java's integer division, really also a floor function in math.

However, what you are doing in the odd case is multiplying in another factor of temp, which is already calculated to be baseexp/2.

Multiply retVal by base, not temp. Change in pow2

retval *= temp;

to

retval *= base;

Additionally, another optimization would be instead of going back to the raise method after dividing exp by 2 in pow2, you can keep going with recursion, repeatedly calling pow2 until you reach a base case of an exponent of 1 or 0.

Upvotes: 2

Related Questions