RFR: 8341470: BigDecimal.stripTrailingZeros() optimization [v35]

[Raffaello Giulietti]

On Thu, 10 Oct 2024 20:36:26 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> An optimized algorithm for `BigDecimal.stripTrailingZeros()` that uses repeated squares trick.
>
> fabioromano1 has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Refining mathematical definition of remainingZeros

src/java.base/share/classes/java/math/BigDecimal.java line 5221:

> 5219:      * {@code FIVE_TO_2_TO[n] == 5^(2^n)}
> 5220:      */
> 5221:     private static final BigInteger[] FIVE_TO_2_TO = new BigInteger[20];

As discussed before, the benchmarks show no significant performance regressions even for a million of trailing zeros if this cache is reduced to save resident memory footprint.
Suggestion:

    private static final BigInteger[] FIVE_TO_2_TO = new BigInteger[16 + 1];

src/java.base/share/classes/java/math/BigDecimal.java line 5259:

> 5257:         preferredScale = Math.clamp(preferredScale, Integer.MIN_VALUE - 1L, Integer.MAX_VALUE);
> 5258:         int powsOf2 = intVal.getLowestSetBit();
> 5259:         // scale - preferredScale >= remainingZeros >= max{n : (intVal % 10^n) == 0 && scale - n >= preferredScale}

Suggestion:

        // scale - preferredScale >= remainingZeros >= max{n : (intVal % 10^n) == 0 && n <= scale - preferredScale}

is clearer IMO.

src/java.base/share/classes/java/math/BigDecimal.java line 5274:

> 5272:         remainingZeros = Math.min(remainingZeros, maxPowsOf5);
> 5273: 
> 5274:         BigInteger[] qr; // quotient-remainder pair

The algorithm is clever, but it took me some time to "reverse-engineer" to understand how it works.

If this is described somewhere in the literature, please add a reference.
Otherwise, it needs an explanation in form of comments.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/21323#discussion_r1797255797
PR Review Comment: https://git.openjdk.org/jdk/pull/21323#discussion_r1797255851
PR Review Comment: https://git.openjdk.org/jdk/pull/21323#discussion_r1797256459