RFR: 8341402: BigDecimal's square root optimization

[Raffaello Giulietti]

On Wed, 2 Oct 2024 16:32:47 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> src/java.base/share/classes/java/math/BigDecimal.java line 2213:
>> 
>>> 2211: 
>>> 2212:                 BigDecimal working = new BigDecimal(this.intVal, this.intCompact, (int) workingScale, this.precision);
>>> 2213:                 BigInteger workingInt = working.toBigInteger();
>> 
>> @rgiulietti The cause of slow running time starts here: casting to `BigInteger` requires to multiply by a power of 10, and if the power of 10 is large, then the multiplication costs much time, as does computing the square root of the large resulting number.
>
> @rgiulietti The only solution I can think of to avoid this is to reimplement Zimmerman's square root algorithm in the class `BigDecimal`, using the radix 10 representation of the number's magnitude.

After looking at the code more closely, these are _not_ the reasons for the long running times of my example above.
Neither the computation of the large power of 10, nor the multiplication, nor the `BigInteger` square root are slow.

The slowdown in my example of sqrt(121) above comes from the call to `stripZerosToMatchScale()`, which performs about a million divisions by 10 to meet the preferred scale.

In fact, when there are no trailing zeros in the result, the running times are very fast.
Replacing 121 (an exact square) with 122 in the example above reduces the time to less than 1 s rather than more than 3 min, because there are no trailing zeros to get rid of:
`BigDecimal.valueOf(121).sqrt(new MathContext(1_000_000, RoundingMode.HALF_EVEN))` more than 3 min
`BigDecimal.valueOf(122).sqrt(new MathContext(1_000_000, RoundingMode.HALF_EVEN))` less than 1 s

Of course, this is not the fault of `BigDecimal.sqrt()`, but of the way `stripZerosToMatchScale()` is implemented. Maybe the topic of your next PR ;-) ? Might be hard, though.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/21301#discussion_r1784953613