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 O(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 an n x n
digit multiplication. Which I believe is O(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 love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With