What are complexities of BigInteger.pow and BigInteger.isProbablePrime?
What are complexities of Java 7's methods pow
and isProbablePrime
in the BigInteger
class?
I know that simple implementation of Rabin's test is of 开发者_如何学JAVAO(k(log(n))^3) complexity and that can be reduced by incorporating the Schönhage-Strassen algorithm for the fast multiplication of long integers.
Assuming the standard algorithms, the complexities are:
pow() : O( M(n * exponent) )
IsProbablePrime() : O( M(n) * n )
where:
n
is the number of digits in the operand.exponent
is the exponent of the power function.M(n)
is the run-time for ann x n
digit multiplication. Which I believe isO(n^2)
as of Java 6.
Explanation for pow()
:
For an input operand of n-digits long raised to a power of exp
, the output is roughly n * exp
digits long. This is done by binary-powering algorithm where the operand is squared at each iteration. So the complexity becomes:
O( M(n) + M(2*n) + M(4*n) + ... M(n * exp/2) ) = O( M(n * exp) )
This is a geometric sum, so the sum becomes O( M(n * exp) )
.
Explanation for IsProbablePrime()
:
For a fixed number of Rabin-Miller iterations, each iteration has O(n)
multiplications of size n x n
digits. Therefore, the complexity becomes O( n * M(n) )
.
The short answer is that it isn't specified and therefore subject to implementor's choice.
If you want to have a look at the source, here it is: http://futureboy.us/temp/BigInteger.java.
Relevant material to your question here too: What complexity are operations on Java 7's BigInteger?
精彩评论