RFR: 4837946: Faster multiplication and exponentiation of large integers [v19]

[Raffaello Giulietti]

On Thu, 24 Apr 2025 20:18:42 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> @fabioromano1 I just had a cursory glance at this PR.
>> 
>> AFAIU, there are two main contributions here:
>> 
>> - Performance enhancements in `pow()`, which is of general interest and does not require submitting a [CSR](https://wiki.openjdk.org/display/csr/Main).
>> - Introduction of a new public API point for the _n_-th root, which would require a CSR.
>> 
>> It's important to understand that if we add public API points, there must be some evidence and consensus about their general usefulness and demand for them. Every addition is a commitment for this community in terms of code maintenance, reviews, testing, documentation, so they should be evaluated with this perspective in mind.
>> 
>> In this case, I feel that the proposed _n_-th root might not be among the top priority API points to add to `BigInteger`. Perhaps the overall plan is to use this method to implement a _n_-th root in `BigDecimal` in some followup PR, but this is not stated here.
>> 
>> Anyway, a [preliminary discussion](https://openjdk.org/guide/#socialize-your-change) about the proposal should take place on the mailing list, _before_ submitting the PR and invest too much work on the code.
>> 
>> To make progress here, I suggest to split this PR in two, if technically possible:
>> 
>> - One for the enhancements in `pow`, with JMH results before/after.
>> - Another PR for the proposed _n_-th root.
>> 
>> Thanks
>
>> * Performance enhancements in `pow()`, which is of general interest and does not require submitting a [CSR](https://wiki.openjdk.org/display/csr/Main).
> 
> @rgiulietti Yes, but here, the primary enhancement in `pow()` is not concerned most on execution time, but rather in memory optimization, because the PR implementation does the "shift of the exponent" squaring the result rather than the base, so the base is not squared like in the current implementation, and this permits to save about half of the memory.
> 
>> To make progress here, I suggest to split this PR in two, if technically possible:
>> 
>> * One for the enhancements in `pow`, with JMH results before/after.
>> * Another PR for the proposed _n_-th root.
> 
> I'm not very sure if it is technically possible, because both `pow()` and `nthRoot()` requires the computation of a power of a long, so that code has to be shared by both methods, and so a supposed PR for `nthRoot()` would require that method.

@fabioromano1 What's going on here? I guess this splits the original PR in two parts, as suggested?
It would be better to discuss such matters before submitting a PR.

I created a new JBS issue to refer to.
https://bugs.openjdk.org/browse/JDK-8355719
Let me know if the new title and the description convey the gist of the PR.

The current JBS issue is about speed improvements in multiplication and exponentiation, and is closed as Resolved since more than 10 years.
Please adjust the PR accordingly, by changing the title.

Also, your claims about memory consumption reduction should be supported by evidence using [JMH](https://github.com/openjdk/jmh/) benchmarks.
See [this sample](https://github.com/openjdk/jmh/blob/master/jmh-samples/src/main/java/org/openjdk/jmh/samples/JMHSample_35_Profilers.java) for how to measure memory allocation rates.

-------------

PR Comment: https://git.openjdk.org/jdk/pull/24690#issuecomment-2835377026