RFR: 8341402: BigDecimal's square root optimization

[fabioromano1]

On Wed, 2 Oct 2024 16:15:29 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.
>
> 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.

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

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