Geek Answers Handbook

What are the difficulties of BigInteger.pow and BigInteger.isProbablePrime?

What are the complexities of the Java 7 pow and isProbablePrime in the BigInteger class?

I know that a simple implementation of the Rabin test has complexity O (k (log (n)) ^ 3) and can be reduced by including the Schönhage-Strassen algorithm for quickly multiplying long integers.

+4
source share
3 answers

Assuming standard algorithms, the difficulties are:

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

Where:

  • n is the number of digits in the operand.
  • exponent is an exponent of a power function.
  • M(n) is the runtime to multiply the digits nxn . I believe O(n^2) compared to Java 6.

Explanation for pow() :

For an input operand with n-characters long, increased to exp , the output will be approximately n * exp digits long. This is done by the binary power algorithm, where the operand is quadratized at each iteration. Thus, 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) multiplication digits nxn . Therefore, the complexity becomes O( n * M(n) ) .

+4
source

The short answer is that it is not specified and therefore can be chosen by the developer.

+3
source

If you want to see the source, here it is: http://futureboy.us/temp/BigInteger.java .

Relevant material to your question here: What is the complexity of operations with BigInteger Java 7?

0
source

More articles:


All Articles