I'm planning on tackling the performance issues in the BigInteger class. In short, inefficient algorithms are used for multiplication, exponentiation, conversion to strings, etc. I intend to improve this by adding algorithms with better asymptotic behavior that will work better for large numbers, while preserving the existing algorithms for use with smaller numbers.
This encompasses a lot of different bug reports: 4228681: Some BigInteger operations are slow with very large numbers http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4228681 (This was closed but never fixed.) 4837946: Implement Karatsuba multiplication algorithm in BigInteger http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946 I've already done the work on this one. My implementation is intended to be easy to read, understand, and check. It significantly improves multiplication performance for large numbers. 4646474: BigInteger.pow() algorithm slow in 1.4.0 http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474 This will be improved in a couple ways: * Rewrite pow() to use the above Karatsuba multiplication * Implement Karatsuba squaring * Finding a good threshhold for Karatsuba squaring * Rewrite pow() to use Karatsuba squaring * Add an optimization to use left-shifting for multiples of 2 in the base. This improves speed by thousands of times for things like Mersenne numbers. 4641897: BigInteger.toString() algorithm slow for large numbers http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897 This algorithm uses a very inefficient algorithm for large numbers. I plan to replace it with a recursive divide-and-conquer algorithm devised by Schoenhage and Strassen. I have developed and tested this in my own software. This operates hundreds or thousands of times faster than the current version for large numbers. It will also benefit from faster multiplication and exponentiation. In the future, we should also add multiplication routines that are even more efficient for very large numbers, such as Toom-Cook multiplication, which is more efficient than Karatsuba multiplication for even larger numbers. Has anyone else worked on these? Is this the right group? I will probably submit the Karatsuba multiplication patch soon. Would it be more preferable to implement *all* of these parts first and submit one large patch? -- Alan Eliasen | "Furious activity is no substitute [EMAIL PROTECTED] | for understanding." http://futureboy.us/ | --H.H. Williams
