4646474 : BigInteger.pow() algorithm slow in 1.4.0

[Brian Burkhalter]

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