How to calculate 2 to-the-power N where N is a very large number

user_10067128 0
Viewed 273

I need to find 2 to-the-power N where N is a very large number (Java BigInteger type)

Java BigInteger Class has pow method but it takes only integer value as exponent.

So, I wrote a method as follows:

static BigInteger twoToThePower(BigInteger n)
   {
      BigInteger result = BigInteger.valueOf(1L);

      while (n.compareTo(BigInteger.valueOf((long) Integer.MAX_VALUE)) > 0)
      {
         result = result.shiftLeft(Integer.MAX_VALUE);
         n = n.subtract(BigInteger.valueOf((long) Integer.MAX_VALUE));

      }

      long k = n.longValue();
      result = result.shiftLeft((int) k);

      return result;
   }

My code works fine, I am just sharing my idea and curious to know if there is any other better idea?

Thank you.

pow biginteger java
4 Answers

You cannot use BigInteger to store the result of your computation. From the javadoc :

BigInteger must support values in the range -2^Integer.MAX_VALUE (exclusive) to +2^Integer.MAX_VALUE (exclusive) and may support values outside of that range.

This is the reason why the pow method takes an int. On my machine, BigInteger.ONE.shiftLeft(Integer.MAX_VALUE) throws a java.lang.ArithmeticException (message is "BigInteger would overflow supported range").

user_75062520

By using repeated squaring you can achieve your goal. I've posted below sample code to understand the logic of repeated squaring.

static BigInteger pow(BigInteger base, BigInteger exponent) {
    BigInteger result = BigInteger.ONE;
    while (exponent.signum() > 0) {
        if (exponent.testBit(0)) result = result.multiply(base);
        base = base.multiply(base);
        exponent = exponent.shiftRight(1);
    }
    return result;
}
user_93184920

An interesting question. Just to add a little more information to the fine accepted answer, examining the openjdk 8 source code for BigInteger reveals that the bits are stored in an array final int[] mag;. Since arrays can contain at most Integer.MAX_VALUE elements this immediately puts a theoretical bound on this particular implementation of BigInteger of 2(32 * Integer.MAX_VALUE). So even your method of repeated left-shifting can only exceed the size of an int by at most a factor of 32.

So, are you ready to produce your own implementation of BigInteger?

user_2387040

Emmanuel Lonca's answer is correct. But, by Manoj Banik's idea, I would like to share my idea too.

My code do the same thing as Manoj Banik's code in faster way. The idea is init the buffer, and put the bit 1 in to correct location. I using the shift left operator on 1 byte instead of shiftLeft method.
Here is my code:

    static BigInteger twoToThePower(BigInteger n){
        BigInteger eight = BigInteger.valueOf(8);
        BigInteger[] devideResult = n.divideAndRemainder(eight);
        BigInteger bufferSize = devideResult[0].add(BigInteger.ONE);
        int  offset = devideResult[1].intValue();
        byte[] buffer = new byte[bufferSize.intValueExact()];
        buffer[0] = (byte)(1 << offset);
        return new BigInteger(1,buffer);
    }

But it still slower than BigInteger.pow

Then, I found that class BigInteger has a method called setBit. It also accepts parameter type int like the pow method. Using this method is faster than BigInteger.pow.
The code can be:

    static BigInteger twoToThePower(BigInteger n){
        return BigInteger.ZERO.setBit(n.intValueExact());
    }

Class BigInteger has a method called modPow also. But It need one more parameter. This means you should specify the modulus and your result should be smaller than this modulus. I did not do a performance test for modPow, but I think it should slower than the pow method.

user_76145880
Related