7

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.

Joachim Sauer
  • 302,674
  • 57
  • 556
  • 614
Pedja
  • 373
  • 4
  • 14
  • 3
    Have you looked at the source code? Or do you expect us to do it for you? – Stephen C Oct 03 '11 at 06:42
  • Have they improved the multiplication to sub-quadratic yet? Last time I checked it was still `O(n^2)`. All other major functions depend heavily on the speed of the multiplication. – Mysticial Oct 03 '11 at 06:43
  • 1
    I'd like to note that `pow()` and `isProbablyPrime()` are included since the very first version of `BigInteger` (according to the JavaDoc) and `BigInteger` was introduced in JDK 1.1! So that's by no means a new feature in Java 7. – Joachim Sauer Oct 03 '11 at 06:57
  • @Stephen C: Unless the complexity is explicitly written in the source code, it is not easy to figure it out from just looking at the code. – Mysticial Oct 03 '11 at 07:02
  • @Mysticial - That doesn't address my point. – Stephen C Oct 03 '11 at 12:10

3 Answers3

4

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) ).

Mysticial
  • 464,885
  • 45
  • 335
  • 332
  • Your answer for pow() is wrong, as it is computed via logarithms in the FPU. Nothing to do with multiplication or the number of digits. It would be wrong anyway for exponentation to an integral power, as there are much faster algorithms than just multiplying 'exponent' times. Your answer for isProbablePrime looks like mere guesswork. – user207421 Oct 03 '11 at 07:12
  • 2
    @EJP: The BigInteger pow() function powers an integer to an integer power. There's no floating-point going on here. The result of powering an N-digit integer to an exponent of `m` will result in a number of roughly `N * m` digits long - which are done by large multiplications. – Mysticial Oct 03 '11 at 07:14
  • 1
    But not O(M(n*exponent)) multiplications. BigInteger.pow() uses a square-and-multiply algorithm as described in Knuth ACP vol II #4.6.3. The number of multiplications is O(sqrt(N)). – user207421 Oct 03 '11 at 07:29
  • @EJP: `n*exponent` refers to the size of the operand. So `M(n * exponent)` means the time needed to multiply two numbers of size `n * exponent`. (not the # of multiplicatios - which is obviously `O(log(n))`) Don't forget that large multiplication is not constant. (That's why there's an `M()`) – Mysticial Oct 03 '11 at 07:33
  • So you don't have a factor in there for the number of multiplications at all? – user207421 Oct 03 '11 at 07:36
  • @EJP: It's semi-geometric sum. Each of the subsequent multiplications doubles in size. So the sum ends up being a constant factor with respect to the largest multiplication. (the last one) – Mysticial Oct 03 '11 at 07:37
3

The short answer is that it isn't specified and therefore subject to implementor's choice.

user207421
  • 305,947
  • 44
  • 307
  • 483
0

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?

Community
  • 1
  • 1
Savino Sguera
  • 3,522
  • 21
  • 20