RFR: 8341402: BigDecimal's square root optimization

[Raffaello Giulietti]

On Wed, 2 Oct 2024 18:06:57 GMT, fabioromano1 <duke at openjdk.org> wrote:

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

Without experimenting a bit, it's hard to tell.
Anyway, I believe the current implementation of `stripZerosToMatchScale()` is O(n^2) rather than exponential, because each single division by 10 is linear.

But let's focus on `sqrt()` in this PR and leave `stripZerosToMatchScale()` for another time.

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

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