0

I am aware that there are three ways transform and conquer can be used to simplify a problem. I'm trying to simplify the code of this one to become more efficient. The thing is, it's already in log n runtime. I was wondering how I could possibly simplify this solution further? It's a recursive divide-and-conquer method in Java for a power algorithm where base = a and n= the exponential power. So basically x^n or A^n. I'm compiling it into codingbat which is why it's structured the way it is(codingbat has certain limitations). Any suggestions?

    public int powerN(int base, int n) {  
      if (n==1)
         return base;

      else if (n==2)
         return base*base;

      else if (n%2==0)
         return powerN(base*base, n/2);


      else if (n%2==1)
         return powerN(base, n-1)* base; 
      else
         return 1;   
    }
user3238590
  • 3
  • 2
  • 2
    You could go `else if (n%2==1) return powerN(base*base, (n-1)/2)* base;` but that would not give you better asymptotics, just one function call less. – G. Bach Apr 30 '14 at 12:11
  • Although it is not exactly the same question, the answers to [this question](http://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int) might help. – Zoyd Apr 30 '14 at 12:18
  • omit the n==2 case, it is redundant. Also, make the base case n == 0 and remove the n==1 base case. Then your code is left with 3 branches instead of five (i suppose you only want to treat positive n?) – kutschkem Apr 30 '14 at 13:26
  • i don't know coding bat but bear in mind that you calculate the same leave types again and again. Cant you somehow pass a hashmap as third parameter where you cache the results of previous calculations – David Michael Gang Apr 30 '14 at 13:48
  • @DavidMichaelGang not really true, there is exactly one "leaf". This is not "divide" and conquer. – kutschkem Apr 30 '14 at 14:12
  • I understand. In order to make it quicker you could save the Calculation of square base which is your Implicit second leaf – David Michael Gang Apr 30 '14 at 19:21

0 Answers0