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

Мне нужно найти 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;
   }

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

Спасибо.


java biginteger pow
person User_67128    schedule 20.06.2019    source источник
comment
Вы можете быстро проверить, если n <= 63, и просто сделать 1L << n.longValue();. Также проверьте наличие n == 0. Но я думаю, если вы скажете, что он всегда большой, в этом может не быть необходимости.   -  person Neijwiert    schedule 20.06.2019
comment
n — это BigInteger, в противном случае я позаботился о небольших значениях. Спасибо хоть.   -  person User_67128    schedule 20.06.2019

Ответы (4)


arrow_upward
1
arrow_downward

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

Мой код делает то же самое, что и код Маноджа Баника, но быстрее. Идея состоит в том, чтобы инициализировать буфер и поместить бит 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.

person Esc Điệp    schedule 20.06.2019
comment
О, да, setBit — лучшая идея для Base = 2, я использовал этот метод ранее. - person User_67128; 20.06.2019

arrow_upward
2
arrow_downward

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

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

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

person Emmanuel Lonca    schedule 20.06.2019
comment
Вы абсолютно правы. Я знал диапазон Java BigInteger, но на мгновение забыл об этом. Так что мне не нужно беспокоиться об этом, хотя моя техника правильная. Спасибо. - person User_67128; 20.06.2019

arrow_upward
1
arrow_downward

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

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;
}
person Dushyant Tankariya    schedule 20.06.2019
comment
Для базы = 2 этот метод будет медленнее. Для другой базы это нормально. Спасибо. - person User_67128; 20.06.2019

arrow_upward
1
arrow_downward

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

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

person President James K. Polk    schedule 20.06.2019
comment
Возможно, я хотел бы реализовать свою программу на С++ с поддержкой библиотеки Boost, отличной от реализации моего собственного BigInteger. - person User_67128; 20.06.2019
comment
Да, я был только наполовину серьезен. Создание реализации BigInteger с нуля требует огромных усилий. - person President James K. Polk; 20.06.2019