RFR: 8341402: BigDecimal's square root optimization

[fabioromano1]

On Wed, 2 Oct 2024 17:37:03 GMT, Raffaello Giulietti <rgiulietti at openjdk.org> wrote:

>> @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.

A possible faster implementation of `stripZerosToMatchScale()` could be based on dividing by increasing powers of 10 whose exponent doubles at each step (a kind of repeated squares trick), although the asymptotic running time would still be exponential.

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

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