4646474 : BigInteger.pow() algorithm slow in 1.4.0 (original) (raw)

Brian Burkhalter brian.burkhalter at oracle.com
Mon May 20 18:26:48 UTC 2013

Thought I sent this last week but it was saved in Drafts …

On May 16, 2013, at 10:48 PM, Alan Eliasen wrote:

Yes, the extreme examples are ones like in the original bug report, which are literally millions of times faster. If the base contains a power of 2, (which is by far the most common case I see in numeric algorithms,) then performance can be be so drastically improved that it's hard to measure the actual ratio. For example, you've seen the workarounds in BigDecimal for slow 10^x calculations, which will be greatly improved by this patch and the toString() changes in the next phase.

Note that when Schoenhage-Strassen multiplication is included, the ratio will be even better. On an eight-core (using just one core) AMD FX-8350 at 4 GHz, the time for your example of 17^13466917 drops from 1412.522 seconds to 15.233 seconds, an improvement of a factor of about 93.

Great!

I linked this issue to 4837946 as a duplicate so it will be closed out at the same time. That'll be great to see. Combined, these two bug reports are old enough to buy us drinks. I'm so proud of them. :)

Dry vodka martini or single malt?

Is there any plan to backport these to earlier JVMs?

That would be decided by the release team for the VM version in question. Unfortunately the JDK 8 version of BigInteger prior to applying the phase 1 changes already has nearly 600 lines of diffs versus the JDK 7 repository version. Some of these changes (new public APIs for example) would not be amenable to backporting. I think however that the phase 1 changes are mostly if not entirely disjoint with the other post-7 changes, so I doubt that the presence of these other diffs would be an impediment. I would prefer however to get the code integrated into the JDK 8 train first and some time subsequently worry about any backports.

Brian

More information about the core-libs-dev mailing list