Как рассчитать 2 к власти N, где N - очень большое число

Question

Мне нужно найти 2 к власти N, где N - очень большое число (тип Java BigInteger)

Класс Java BigInteger имеет метод pow, но он принимает только целочисленное значение в качестве показателя степени.

Итак, я написал метод следующим образом:

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;
   }

Мой код работает нормально, я просто делюсь своей идеей и хочу узнать, есть ли какая-нибудь другая лучшая идея?

Спасибо.

Answer 1

Вы не можете использовать BigInteger для хранения результатов ваших вычислений.От javadoc:

BigInteger должен поддерживать значения в диапазоне от -2 ^ Integer.MAX_VALUE (эксклюзив) до + 2 ^ Integer.MAX_VALUE (эксклюзив) и может поддерживать значения вне этого диапазона.

Это причина, почему метод pow принимает int.На моей машине BigInteger.ONE.shiftLeft (Integer.MAX_VALUE) выдает исключение java.lang.ArithmeticException (сообщение «BigInteger переполнит поддерживаемый диапазон»).

Answer 2

Эммануэль Лонка ответ правильный. Но, по идее Маноджа Баника, я тоже хотел бы поделиться своей идеей.

Мой код делает то же самое, что и код Маноя Баника, более быстрым способом. Идея состоит в том, чтобы инициализировать буфер и поместить бит 1 в правильное местоположение. Я использовал оператор сдвига влево на 1 байт вместо shiftLeft метода.
Вот мой код:

    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);
    }

Но все равно медленнее, чем BigInteger.pow

Затем я обнаружил, что у класса BigInteger есть метод с именем setBit. Он также принимает тип параметра int как метод pow. Использование этого метода быстрее, чем BigInteger.pow.
Код может быть:

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

Класс BigInteger также имеет метод с именем modPow. Но для этого нужен еще один параметр. Это означает, что вы должны указать modulus, и ваш результат должен быть меньше, чем этот modulus. Я не делал тест производительности для modPow, но думаю, что он должен быть медленнее, чем метод pow.

Answer 3

интересный вопрос. Просто чтобы добавить немного больше информации к хорошо принятому ответу, изучение исходного кода openjdk 8 для BigInteger показывает, что биты хранятся в массиве final int[] mag;. Поскольку массивы могут содержать не более Integer.MAX_VALUE элементов, это немедленно устанавливает теоретическую границу для этой конкретной реализации BigInteger, равную 2 ^{(32 * Integer.MAX_VALUE)} . Таким образом, даже ваш метод повторного сдвига влево может превышать только размер int не более чем в 32 раза.

Итак, вы готовы создать собственную реализацию BigInteger?

Answer 4

Используя повторное возведение в квадрат, вы можете достичь своей цели. Ниже приведен пример кода, чтобы понять логику повторного возведения в квадрат.

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;
}