RFR: 8341402: BigDecimal's square root optimization

[Raffaello Giulietti]

On Wed, 2 Oct 2024 10:31:09 GMT, fabioromano1 <duke at openjdk.org> wrote:

> After changing `BigInteger.sqrt()` algorithm, this can be also used to speed up `BigDecimal.sqrt()` implementation. Here is how I made it.
> 
> The main steps of the algorithm are as follows:
> first argument reduce the value to an integer using the following relations:
> 
> x = y * 10 ^ exp
> sqrt(x) = sqrt(y) * 10^(exp / 2) if exp is even
> sqrt(x) = sqrt(y*10) * 10^((exp-1)/2) is exp is odd
> 
> Then use BigInteger.sqrt() on the reduced value to compute the numerical digits of the desired result.
> 
> Finally, scale back to the desired exponent range and perform any adjustment to get the preferred scale in the representation.

This takes more than 3 minutes on my laptop, although it is faster than the current implementation:
`BigDecimal.valueOf(121).sqrt(new MathContext(1_000_000, RoundingMode.HALF_EVEN)).shortValue()`

I think the running time is dominated by the back scaling, which involves a division by a large power of 10.

I wonder if scaling up and down by an appropriate combination of large powers of 2 and small powers of 10 might improve performance for such high precision. The combination should, of course, minimally cover the requested precision. Final corrective steps might be needed, though.

Curiously, this one runs in a fraction of a second on the current implementation, but not on the proposed one:
`BigDecimal.valueOf(100).sqrt(new MathContext(1_000_000, RoundingMode.HALF_EVEN)).shortValue()`

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

PR Comment: https://git.openjdk.org/jdk/pull/21301#issuecomment-2388683885