Performing two sequential BigDecimal exponentiations hangs

[JoonasC]

Describe the bug When performing two sequential BigDecimal exponentiations, the second exponentiation will hang.

To Reproduce Run the following code:

val decimalMode = DecimalMode(6L, RoundingMode.CEILING, -1L)

val a = BigDecimal.parseStringWithMode("-8.40575E+306", decimalMode)
val b = BigDecimal.parseStringWithMode("-1.77408E+308", decimalMode)

a.pow(b.longValue(false))

val c = BigDecimal.parseStringWithMode("-3.74044E+307", decimalMode)
val d = BigDecimal.parseStringWithMode("-2.22553E+8", decimalMode)

c.pow(d.longValue(false)) // Hangs here

Expected behavior Both exponentiations complete without issue.

Platform JVM and JS

Additional context For me this occurs on a multiplatform project with the browser JS and JVM targets.

[ionspin]

Thanks for reporting!

[ionspin]

Hi @JoonasC, Sorry for getting back to this just now, I didn't have time to tackle it sooner. It did take me some time to unravel what was happening, and I found some other corner cases to fix while looking at this, so that's good.

So on to your example, in the first case when you are narrowing the b to a long, the result is going to be 0, because the longValue is similar to Javas BigInteger (which was inspiration for the most of the library) and is just returning the lower 63 bits (and unlike Javas BigInteger preserves the sign)

In this particular case when "-1.77408E+308" is expanded, several least significant words are 0 and therefore the lowest 63 bits are 0.

This makes the pow to immediately return 1 as the result of operation

In your second part of the example, this doesn't happen and the calculations start, but it doesn't hang as far as I have tested, it just takes a lot of time, I don't know how much.

I tried to replicate that exponentiation with Java BigInteger, but it has a hard limit and throws an exception. This code is from Java BigDecimal:

public BigDecimal pow(int n) {
        if (n < 0 || n > 999999999)
            throw new ArithmeticException("Invalid operation");
        // No need to calculate pow(n) if result will over/underflow.
        // Don't attempt to support "supernormal" numbers.
        int newScale = checkScale((long)scale * n);
        return new BigDecimal(this.inflated().pow(n), newScale);
    }

[JoonasC]

@ionspin Well, what I meant by hanging was that it didn't seem to be terminating. I waited for 30 minutes, but it still wasn't terminating. I think it's safe to assume it would go on forever.

[ionspin]

Could you then clarify what would you like to see the library do?

[JoonasC]

I would expect the library to stop at some point, at the moment though it's not stopping. I'm not on my computer at the moment, but you can try to replace the c and d operation with a and b, essentially performing a and b two times in a row. And if I'm right the second time should also not terminate.

[ionspin]

I would expect the library to stop at some point

It's unclear what would be the stopping criteria you are proposing.

I'm not on my computer at the moment, but you can try to replace the c and d operation with a and b, essentially performing a and b two times in a row. And if I'm right the second time should also not terminate.

I wouldn't expect a long running operation to terminate before it's done with calculations, or it runs out of memory.

[JoonasC]

What I'm saying is that it seems to me like the library goes into an infinite loop, but I might be wrong. I'll need to test this again.

[ionspin]

What I'm saying is that it seems to me like the library goes into an infinite loop, but I might be wrong. I'll need to test this again.

Ah, that's where our misunderstanding was. Please update here after you test, I unfortunately don't have any more time to work on the library today. Cheers, and have a great rest of the weekend!

[JoonasC]

@ionspin Ok, you were right.

It seems like it just takes a long time.

[JoonasC]

Is it normal for it to take such a long time with a precision of 6 being enforced though?

[JoonasC]

Btw, if you're wondering how I'm getting those values which cause issues, I'm using a testing framework called Kotest.

Specifically, I'm using the property tests feature of Kotest.

[ionspin]

I honestly have no clear picture what would be the acceptable time frame for those values. I tried to replicate using Java, but as I said they won't even let you try exponentiation above that arbitrary looking value (999999999). With that said, there is a LOT of room for improvement regarding time and memory usage, especially when considering divisions, which we have here. You might have more luck by implementing an expect/actual interface and then using platform libraries, which would presumably have much better performance.

I have planned to have native/platform implementations for version 0.5.0, which would help optimize, but that's a long way away, as I see higher priority in stabilizing the API with version 0.4.0 before diving in into optimizations. So probably next year or the one after.

Also I saw somewhere (an issue on kotlin tracker but I can't remember which one) that JetBrains is implementing their own multiplatform bignum library, so that might work better when it comes out.