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

[fabioromano1]

On Wed, 30 Apr 2025 12:20:39 GMT, Raffaello Giulietti <rgiulietti at openjdk.org> wrote:

>> fabioromano1 has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   Simplified the formula for detecting overflows
>
> 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 Probably the `powerCache` array is needless because the number of iterations is very low. Perhaps using `Math.pow(int, int)` could be a faster way to get the powers, since it reduces the number of iterations further and it has constant time, although even the traditional "repeated square" method has constant time...

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

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