Каковы сложности BigInteger.pow и BigInteger.isProbablePrime?

Question

Каковы сложности методов Java 7 pow а также isProbablePrime в BigInteger учебный класс?

Я знаю, что простая реализация теста Рабина имеет сложность O(k(log(n))^3) и может быть уменьшена путем включения алгоритма Шёнхаге-Штрассена для быстрого умножения длинных целых чисел.

Answer 1

Предполагая стандартные алгоритмы, сложности:

pow()             : O( M(n * exponent) )
IsProbablePrime() : O( M(n) * n )

где:

• n количество цифр в операнде.
• exponent показатель степени степенной функции.
• M(n) это время выполнения для n x n умножение цифр. Который я считаю O(n^2) с Java 6.

Объяснение для pow() :

Для входного операнда из n-значных длин, возведенных в степень exp выход примерно n * exp цифры длинные. Это делается с помощью алгоритма двоичного питания, где операнд возводится в квадрат на каждой итерации. Таким образом, сложность становится:

O( M(n) + M(2*n) + M(4*n) + ... M(n * exp/2) ) = O( M(n * exp) )

Это геометрическая сумма, поэтому сумма становится O( M(n * exp) ),

Объяснение для IsProbablePrime() :

Для фиксированного числа итераций Рабина-Миллера каждая итерация имеет O(n) умножения размера n x n цифры. Следовательно, сложность становится O( n * M(n) ),

Answer 2

Краткий ответ: он не указан и, следовательно, зависит от выбора разработчика.

Answer 3

Если вы хотите взглянуть на источник, вот он: http://futureboy.us/temp/BigInteger.java.

Соответствующий материал для вашего вопроса здесь также: Какова сложность операций на Java 7 BigInteger?