On Wed, 2 Oct 2024 18:06:57 GMT, fabioromano1 <d...@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
