Power function in Java using recursion

Question

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.

Here, made an Ideone for you: ideone.com/b4d5LN I also suggest you add comments to your code, to explain what the logic behind some of your descisions are. Usually stepping manually through your code, trying to explain every step will force you to run the code through your head, and helps finding logic flaws. — Tschallacka
– Tschallacka, Commented Jan 29, 2018 at 17:46
no need for raise() and pow2() methods. Just call pow1(base,exp) from main(). It will return count of multiplications as 19 mind. Then you can add memoization to pow1() to limit multiplications. — diginoise
– diginoise, Commented Jan 29, 2018 at 18:10

rgettman · Accepted Answer · 2018-01-29 17:54:49Z

2

It looks like you are attempting to make the optimization:

base^exp = base^exp/2 * base^exp/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 base^exp/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.

answered Jan 29, 2018 at 17:54

rgettman

179k30 gold badges282 silver badges365 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

javardee Over a year ago

This is exactly what I was looking for. Thank you so much! retval *= base works perfect.

Roberto Trani · Accepted Answer · 2018-01-29 18:00:25Z

1

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.

answered Jan 29, 2018 at 18:00

Roberto Trani

1,23711 silver badges15 bronze badges

Collectives™ on Stack Overflow

Power function in Java using recursion

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related