Finding A power B using BigInteger and using recursion

Question

This is the 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 is should work for any value of b considering that its a BigInteger. But when i enter very large value of b ,i get errors as

Exception in thread "main" java.lang.StackOverflowError
    at java.math.MutableBigInteger.divideKnuth(Unknown Source)
    at java.math.MutableBigInteger.divideKnuth(Unknown Source)
    at java.math.BigInteger.remainderKnuth(Unknown Source)
    at java.math.BigInteger.remainder(Unknown Source)
    at java.math.BigInteger.mod(Unknown Source)

Is there a way to fix it?

What big number ? since you divid by 2, this might take some call to get to 1 leading to this stackoverflow (and leading you on SO). This is a lot of BigInteger to store in memory — AxelH
– AxelH, Commented Nov 10, 2016 at 7:16
FYI: n.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO)==0 is better written as !n.testBit(0), and n.divide(BigInteger.valueOf(2)) is better written as n.shiftRight(1). Performs much better. — Andreas
– Andreas, Commented Nov 10, 2016 at 7:19
Question: Why are you trying to raise a long value to a BigInteger exponent, and only returning result as a long? If the base is 1, result is 1 no matter the exponent. If base is 2, the result will overflow the supported range of a long result for an exponent value of 63, and you hardly need a BigInteger to that kind of value. For bases higher than 2, the result will overflow long at even smaller exponent values. Your method makes no sense. — Andreas
– Andreas, Commented Nov 10, 2016 at 7:27
But if i dont use Recursion then the computation will go up by a lot of factor .Variable b can be anything. — Rajat Seeddharth
– Rajat Seeddharth, Commented Nov 10, 2016 at 7:28

xenteros · Accepted Answer · 2016-11-10 08:43:47Z

1

You should implement the 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 will drastically reduce the number of calls you're using. Another thing is enlarging the size of the stack. Run your application with java Test -Xss2048k - try different sizes.

And last but not the least use BigInteger all the 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());
 }

edited Nov 10, 2016 at 8:43

answered Nov 10, 2016 at 7:49

xenteros

15.9k12 gold badges59 silver badges93 bronze badges

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

12 Comments

Rajat Seeddharth Over a year ago

it wont work..there are lot of glitches in the code.

xenteros Over a year ago

@RickySterling why won't it work? It's a correct algorithm. You can convert the returned value to long outside the function - single-responsibility.

Rajat Seeddharth Over a year ago

@xenteros...if possible post the whole program using main().I am writing a program for a competition .Its to be compiled using online compiler.

xenteros Over a year ago

@RickySterling what are you exptected to return? Should I print the result of 2^80?

xenteros Over a year ago

Of course it does. Such huge calculations are very time consuming. Give it some time.

|

Collectives™ on Stack Overflow

Finding A power B using BigInteger and using recursion

1 Answer 1

12 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

12 Comments

Your Answer

Sign up or log in

Post as a guest

Related