What complexity are operations on Java 7's Big

Question

What complexity are the methods multiply, divide and pow in BigInteger currently? There is no mention of the computational complexity in the documentation (nor anywhere else).

Answer 1

Measure it. Do operations with linearly increasing operands and draw the times on a diagram. Don't forget to warm up the JVM (several runs) to get valid benchmark results.

If operations are linear O(n), quadratic O(n^2), polynomial or exponential should be obvious.

EDIT: While you can give algorithms theoretical bounds, they may not be such useful in practice. First of all, the complexity does not give the factor. Some linear or subquadratic algorithms are simply not useful because they are eating so much time and resources that they are not adequate for the problem on hand (e.g. Coppersmith-Winograd matrix multiplication). Then your computation may have all kludges you can only detect by experiment. There are preparing algorithms which do nothing to solve the problem but to speed up the real solver (matrix conditioning). There are suboptimal implementations. With longer lengths, your speed may drop dramatically (cache missing, memory moving etc.). So for practical purposes, I advise to do experimentation.

The best thing is to double each time the length of the input and compare the times. And yes, you do find out if an algorithm has n^1.5 or n^1.8 complexity. Simply quadruple the input length and you need only the half time for 1.5 instead of 2. You get again nearly half the time for 1.8 if you multiply the length 256 times.

Answer 2

If you look at the code for BigInteger (provided with JDK), it appears to me that multiply(..) has O(n^2) (actually the method is multiplyToLen(..)). The code for the other methods is a bit more complex, but you can see yourself.

Note: this is for Java 6. I assume it won't differ in Java 7.

Answer 3

There is a new "better" BigInteger class that is not being used by the sun jdk for conservateism and lack of useful regression tests (huge data sets). The guy that did the better algorithms might have discussed the old BigInteger in the comments.

Here you go http://futureboy.us/temp/BigInteger.java