'(BigDecimal(1) to BigDecimal(s"1.${"0" * 32}1") by BigDecimal(s"0.${"0" * 33}1")).toList' cause infinite loop in Scala 2.13.0-M5

[xuwei-k]

I think there are two reasons.

1. Use MathContext in BigDecimal operations
2. NumericRange.NumericRangeIterator

not infinite loop when toArray because toArray does not use NumericRange#iterator.

Welcome to Scala 2.13.0-M5 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_181).
Type in expressions for evaluation. Or try :help.

scala> (BigDecimal(1) to BigDecimal(s"1.${"0" * 32}1") by BigDecimal(s"0.${"0" * 33}1")).toArray
res0: Array[scala.math.BigDecimal] = Array(1, 1.000000000000000000000000000000000, 1.000000000000000000000000000000000, 1.000000000000000000000000000000000, 1.000000000000000000000000000000000, 1.000000000000000000000000000000000, 1.000000000000000000000000000000000, 1.000000000000000000000000000000000, 1.000000000000000000000000000000000, 1.000000000000000000000000000000000, 1.000000000000000000000000000000000)

toArray result different from Scala 2.12.x due to MathContext changes

Welcome to Scala 2.12.6 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_181).
Type in expressions for evaluation. Or try :help.

scala> (BigDecimal(1) to BigDecimal(s"1.${"0" * 32}1") by BigDecimal(s"0.${"0" * 33}1")).toArray
res0: Array[scala.math.BigDecimal] = Array(1.0000000000000000000000000000000000, 1.0000000000000000000000000000000001, 1.0000000000000000000000000000000002, 1.0000000000000000000000000000000003, 1.0000000000000000000000000000000004, 1.0000000000000000000000000000000005, 1.0000000000000000000000000000000006, 1.0000000000000000000000000000000007, 1.0000000000000000000000000000000008, 1.0000000000000000000000000000000009, 1.0000000000000000000000000000000010)

BigDecimal#+ difference Scala 2.12 <=> 2.13

scala> new java.math.BigDecimal(1).add(new java.math.BigDecimal(s"0.${"0" * 33}1")) // Scala 2.12.x BigDecimal#+
res0: java.math.BigDecimal = 1.0000000000000000000000000000000001

scala> res0 compareTo (new java.math.BigDecimal(1))
res1: Int = 1

scala> new java.math.BigDecimal(1).add(new java.math.BigDecimal(s"0.${"0" * 33}1"), java.math.MathContext.DECIMAL128)  // Scala 2.13.x BigDecimal#+
res2: java.math.BigDecimal = 1.000000000000000000000000000000000

scala> res2 compareTo (new java.math.BigDecimal(1)) // this cause infinite loop in NumericRangeIterator
res3: Int = 0

• DECIMAL128 is default MathContext in scala.BigDecimal https://github.com/scala/scala/blob/v2.12.6/src/library/scala/math/BigDecimal.scala#L30
• scala.BigDecimal#equals use java.math.BigDecimal#compareTo not java.math.BigDecimal#equals
  • https://github.com/scala/scala/blob/v2.12.6/src/library/scala/math/BigDecimal.scala#L534
  • https://github.com/scala/scala/blob/v2.12.6/src/library/scala/math/BigDecimal.scala#L445

[SethTisue]

it's been a long day. I seem to have pushed a number of commits to various repos referencing "11152" (this bug) that should have referenced #11125. sigh

[Ichoran]

The issues surrounding BigDecimal are complicated for several reasons.

• The Scala implementation of BigDecimal carries a MathContext around with it.
  1. The principle of least surprise suggests that if you set a MathContext, you expect it to be used.
  2. Most operations are binary, so there are two MathContexts, and though the left-hand one seems more natural to use, it's not entirely clear this should be so.
  3. Often, the user neither sets nor is thinking about this MathContext at all.
• Not all arithmetic operations are as "bad" as others when using unlimited precision, but unlimited precision is in general unworkable:
  1. Division is a disaster, due to infinite decimal expansions of common fractions.
  2. Multiplication is okay for one operation, but grows exponentially in the number of operations.
  3. Addition and subtraction are cool if the numbers are vaguely of the same order of magnitude, but not when they are radically different sizes (e.g. 1e10000000 + 1e-100000000).
• If you limit precision, just as with IEEE754 floating-point arithmetic, you end up getting different answers for logically equivalent expressions. This is universally frustrating with IEEE754, and can only partially be avoided with BigDecimal.
• Ranges use numerics in a particularly fiddly way: the expectation is that the increment will actually work, and furthermore, that endpoints will be hit. It also seems reasonable to expect that a calculation of the size of a range does not involve traversing every element (since it's very straightforward arithmetic).

The previous solution to these issues was to use the MathContext for multiplication and division-style operations (since those are the ones with really problematic memory-usage behavior when precision is allowed to grow without bound), but not for addition. This is not a great solution, as evidenced by #10882.

However, the fix #6882 also isn't a great solution as evidenced by this bug, which is that ranges no longer work as expected.

To craft a solution, we need to return to the problematic points again and see what we can do to mitigate as many of them as possible. My suggestion involves thinking more deeply about what the difference is between runaway multiplication, which motivates a fixed MathContext, and "normal" addition, which doesn't run away, and "abnormal" addition where the scales are radically different.

In general, if you can afford M bytes of memory for a number, you can probably also afford 2M, so long as you don't keep doubling with each extra operation. That is, after n operations, you still want the memory to be O(M), not O(2ⁿ M). You also don't want the memory usage to be randomly gigantic if you're adding numbers of vastly different scales. So this suggests to me that the following behavior may be a reasonable compromise:

• Division and multiplication obey whatever MathContext they are given.
• Addition and subtraction can extend precision but only if
  1. Shifting the allowable precision of the smaller number could reach the representable parts of the bigger number (e.g. if limited to 5 digits, 10000 + 1e-4 would work, because if we use up the precision for the second number in the "big" direction it is 0.0001, and that leading zero overlaps the smallest increment representable by 10000)
  2. The extension does not result in having the precision of one side more than twice as great as the other
  3. The shift is necessary to represent the values in the smaller number

There are ways in which this could go wrong--large trees of mixed addition and multiplication could yield numbers that gradually increase and decrease in size, extending precision without bound. However, if you're doing this peculiar operation, you may well want the representation to grow without bound to try to capture the actual value.

Another aspect to consider is whether an explicit MathContext is different than a default one. A default MathContext should try to preserve sensible behavior as much as possible, including things like:

• If you write out a number in full, its MathContext should have sufficient precision to represent it
• Adding vaguely same-sized numbers should work
• Division shouldn't explode everything

This suggests that perhaps an explicit MathContext should be preserved religiously, whereas a floating default MathContext could obey the above rules to try to make mathematics non-surprising.

I haven't looked into whether the operations described here can be computed efficiently so as to not substantially slow down BigDecimal usage.

Alternatively, there are two simpler solutions that we could try:

1. Make the default MathContext bigger than DECIMAL128 (34 digits) to make it less likely that someone would run into it by accident. For instance, one might decide that the diameter of the observable universe measure in Planck lengths (~10⁶²) or the volume of the observable universe in Planck volumes (~10¹⁸⁶) would be sensible upper bounds on precision for all but the most esoteric use cases (e.g. calculating digits of Pi for fun).
2. Special-case NumericRange to override the MathContext of its arguments so that it always can calculate its size appropriately.

I can, if desired, implement any of these things, or perhaps others can. I'd also like some second opinions from people who do this sort of thing more frequently (e.g. @non - you came up with the original compromise; what do you think now?; @NthPortal and @plokhotnyuk and anyone else?).

[plokhotnyuk]

IMO more practical would be depreciation for usage of floating point ranges and make them throwing exception when incremented value is equal to the previous one.

[Ichoran]

Another possibility is to leave the current behavior alone, but add another set of operations for unbounded addition and subtraction, e.g. ++ and --, that would preserve all digits or crash trying. Not sure whether ** is a good idea. Anyway, then NumericRange would have to special-case BigDecimal and use ++ and --.

[Ichoran]

@plokhotnyuk - We already got rid of IEEE754 because there's no way to do ranges properly; but with BigDecimal there is a way to do ranges properly, so it's not very nice to just deprecate that too because we don't feel like it.

The test for whether any incrementing is happening is not entirely trivial, but I guess it could check that it works for the two endpoints. I agree that this would be another way to do it. 10 to 20 by 0 already throws an exception, so I don't think it's a problem to throw an exception if no progress will be made on a range expression.

[adriaanm]

@Ichoran it would be great if you could take care of this one, time permitting

[Ichoran]

@plokhotnyuk - Are you willing to create a PR that checks NumericRange for progress at each end when created, in the case where the numeric has a chance of failure? (Not sure if it should just look for BigDecimal or what.)

Note that the case of partial truncation needs to be considered also. For instance, 1 to 2 by 0.25 gives five values at full precision, but either 6 or 4 with only 2 digits of precision, depending on whether 0.25 is rounded down to 0.2 or up to 0.3.

[plokhotnyuk]

@Ichoran sorry, my shallow understanding of Scala library is not giving me any chance do to it in time for upcoming 2.13.0-RC1

[Ichoran]

All right, I'll take care of it.

[erikerlandson]

Spire unit testing also happens to trip on this. typelevel/spire#759

[SethTisue]

fixed by scala/scala#7670