RFR: 8355719: Reduce memory consumption of BigInteger.pow() [v48]

[Raffaello Giulietti]

On Wed, 30 Apr 2025 14:00:10 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> src/java.base/share/classes/java/math/BigInteger.java line 2737:
>> 
>>> 2735:         }
>>> 2736: 
>>> 2737:         return pow;
>> 
>> Is there a reason this cannot simply be the traditional "repeated square" method?
>> Why this complexity?
>> 
>> Suggestion:
>> 
>>         if (x == 1L)
>>             return 1L;
>> 
>>         if (x == 2L)
>>             return 1L << n;
>> 
>>         /*
>>          * The method assumption means that n <= 40 here.
>>          * Thus, the loop body executes at most 5 times.
>>          */ 
>>         long pow = 1;
>>         for (; n > 1; x *= x, n >>>= 1) {
>>             if ((n & 0b1) != 0) {
>>                 pow *= x;
>>             }
>>         }
>>         return pow * x;
>
> @rgiulietti More than else, since `Math.pow(double, double)` has a lot of optimizations, I expect it to be faster than the simple "repeated square" method...

@fabioromano1 pow(double,double) is quite complex, regardless of whether it is implemented in software or hardware. In fact, it's one of the most complex math functions, one of the reasons being that it takes two arguments.
The implementation invoked in `StrictMath` is more than 200 lines long (including comments).

The "repeated square" slow-path executes ≤ 11 `long` multiplications.
Plus, we need to balance performance and readability.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2068770121