RFR: 8341402: BigDecimal's square root optimization [v31]

[fabioromano1]

On Mon, 10 Feb 2025 09:17:51 GMT, Per Minborg <pminborg at openjdk.org> wrote:

>> fabioromano1 has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   An optimization
>
> This PR seems to be targeting performance, yet no benchmarks are provided comparing the current vs. proposed branch with respect to performance. We need to understand the upside of the proposed changes.

@minborg The essential part of the sqrt algorithms is the actual computing of root's digits. In the PR implementation, this task is performed by calling `BigInteger.sqrt()`, while in the current implementation is done by Newton's iteration loop. The existing benchmarks I've done for `BigInteger.sqrt()` already proved that the current code of `BigInteger.sqrt()`, which implements Zimmermann's sqrt algorithm, is way much faster (`O(n^k)`, if the running time for multiply is `O(n^k)`) than the older implementation of `BigInteger.sqrt()` (`O(n^k log n)`), which also used Newton's method. Since the arithmetic operations are more time-consuming for `BigDecimal`s rather than `BigInteger`s, then it's easy to see that, for the same digit precision, Newton's method is much slower when done with `BigDecimal`s, so this should show that the PR implementation is way much faster than the current implementation of `BigDecimal.sqrt()`.

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

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