java - Finding A power B using BigInteger and using recursion -

this piece of code in java.

import java.util.scanner;  import java.math.*;  class power1 {  public static void main(string[] args) {      scanner in=new scanner(system.in);     long a=in.nextlong();     biginteger b=in.nextbiginteger();     long res=power(a,b);     system.out.println(res); }  public static long power(long x,biginteger n) {      int b=(int)(math.pow(10,9)+7);     long m;     if (n.compareto(biginteger.zero)==0)         return 1;     if(n.compareto(biginteger.one)==0)         return x;     if ((n.mod(biginteger.valueof(2)).compareto(biginteger.zero)==0))     {         m = power(x,n.divide(biginteger.valueof(2)));         return (m * m)%b;     }      else return (x * power(x,n.subtract(biginteger.valueof(1)))%b);  }  } 

this should work value of b considering biginteger. when enter large value of b ,i errors as

exception in thread "main" java.lang.stackoverflowerror     @ java.math.mutablebiginteger.divideknuth(unknown source)     @ java.math.mutablebiginteger.divideknuth(unknown source)     @ java.math.biginteger.remainderknuth(unknown source)     @ java.math.biginteger.remainder(unknown source)     @ java.math.biginteger.mod(unknown source) 

is there way fix it?

you should implement following algorithm:

recursivepower(base, exp):     if (exp == 0)          return 1;     if (exp == 1)         return base;     if (exp%2 == 0) {         temp = recursivepower(base, exp/2);         return temp*temp;     temp = recursivepower(base, (exp-1)/2);     return temp*temp*base; 

this drastically reduce number of calls you're using. thing enlarging size of stack. run application java test -xss2048k - try different sizes.

and last not least use biginteger time.

public static biginteger recursivepower (biginteger base, biginteger exp) {     if (exp.compareto(biginteger.zero) == 0)          return biginteger.one;     if (exp.compareto(biginteger.one) == 0)         return base;     if (exp.mod(biginteger.valueof(2)).compareto(biginteger.zero) == 0) {         biginteger temp = recursivepower(base, exp.divide(biginteger.valueof(2)));         return temp.multiply(temp);     }     biginteger temp = recursivepower(base, (exp.subtract(biginteger.valueof(1)).divide(biginteger.valueof(2))));     return temp.multiply(temp).multiply(base); }  public static void main(string []args){     system.out.println(recursivepower(biginteger.valueof(2), biginteger.valueof(80)).tostring());  }