NumericRange[Double] take and drop are broken #8518

scabug · 2014-04-18T20:04:58Z

scala> val x = 0.0 to 1.0 by 0.1
x: scala.collection.immutable.NumericRange[Double] = NumericRange(0.0, 0.1, 0.2, 0.30000000000000004, 0.4, 0.5, 0.6, 0.7, 0.7999999999999999, 0.8999999999999999, 0.9999999999999999)

scala> x.take(3)
res1: scala.collection.immutable.NumericRange[Double] = NumericRange(0.0, 0.1, 0.2)

scala> x.drop(3)
res2: scala.collection.immutable.NumericRange[Double] = NumericRange(0.30000000000000004, 0.4, 0.5, 0.6, 0.7, 0.7999999999999999, 0.8999999999999999, 0.9999999999999999)

So far so good.

scala> x.drop(3).take(3)
res3: scala.collection.immutable.NumericRange[Double] = NumericRange(0.30000000000000004, 0.4)

Why only two values? Where's 0.5?

scala> x.drop(6)
res4: scala.collection.immutable.NumericRange[Double] = NumericRange(0.6000000000000001, 0.7000000000000001, 0.8, 0.9)

And where did the last value disappear now?

This is all due to floating point representation inaccuracies, but I don't think this is acceptable behavior. x.take(3) should not return a length 2 sequence when x is length 8.

I'll try to make a patch for this over the weekend.

scabug · 2014-04-18T20:04:58Z

Imported From: https://issues.scala-lang.org/browse/SI-8518?orig=1
Reporter: Daniel Darabos (darabos)

scabug · 2014-04-21T19:05:47Z

Daniel Darabos (darabos) said:
I kind of have a fix, just need to address binary compatibility issues. (https://github.com/darabos/scala/commits/SI-8518) In the meanwhile a regression in Scala 2.11 was discovered (#4370). So the situation is even worse now:

scala> 0.0 until 0.2 by 0.1
res0: scala.collection.immutable.NumericRange[Double] = NumericRange(0.0, 0.1)

scala> 0.0 until 0.3 by 0.1
res1: scala.collection.immutable.NumericRange[Double] = NumericRange(0.0, 0.1, 0.2, 0.30000000000000004)

Luckily my change also fixes this issue.

scabug · 2014-04-25T01:06:01Z

@Ichoran said:
scala/scala#3699

I think this is how it has to be fixed--this or another way that chooses exact representations. Unfortunately, the anchor point idea, while it fixes this particular issue, opens up a new one where two apparently identical ranges have different values because they have different anchor points.

Ref scala/bug#8518 Ref scala/bug#9875 Ref scala/bug#9874 NumericRange[Double] has been broken because various parts of the code assumes sane plus operation, which is not possible with Double or Float. Within a few iterations of adding 0.1 or 0.2 it can quickly accumulate floating errors that are surprising. ```scala scala> import collection.immutable.NumericRange import collection.immutable.NumericRange scala> val r = NumericRange.inclusive(1.0, 2.0, 0.2)(scala.math.Numeric.DoubleAsIfIntegral) r: scala.collection.immutable.NumericRange.Inclusive[Double] = NumericRange 1.0 to 2.0 by 0.2 scala> assert(r(3) == r.toList(3), s"${r(3)} != ${r.toList(3)}") java.lang.AssertionError: assertion failed: 1.6 != 1.5999999999999999 scala> val x = NumericRange.inclusive(0.0, 1.0, 0.1)(scala.math.Numeric.DoubleAsIfIntegral) x: scala.collection.immutable.NumericRange.Inclusive[Double] = NumericRange 0.0 to 1.0 by 0.1 scala> x.drop(3).take(3).toList res3: List[Double] = List(0.30000000000000004, 0.4) ``` When encountering Double or Float, this internally uses BigDecimal, which can add numbers without losing precision. This will produce range iterator that looks like `List(1.0, 1.2, 1.4, 1.6, 1.8, 2.0)` when converted into List, as opposed to `List(1.0, 1.2, 1.4, 1.5999999999999999, 1.7999999999999998, 1.9999999999999998)`.

Ref scala/bug#8518 Ref scala/bug#9875 Ref scala/bug#9874 Ref scala/bug#8670 NumericRange[Double] has been broken because various parts of the code assumes sane plus operation, which is not possible with Double or Float. Within a few iterations of adding 0.1 or 0.2 it can quickly accumulate floating errors that are surprising. ```scala scala> import collection.immutable.NumericRange import collection.immutable.NumericRange scala> val r = NumericRange.inclusive(1.0, 2.0, 0.2)(scala.math.Numeric.DoubleAsIfIntegral) r: scala.collection.immutable.NumericRange.Inclusive[Double] = NumericRange 1.0 to 2.0 by 0.2 scala> assert(r(3) == r.toList(3), s"${r(3)} != ${r.toList(3)}") java.lang.AssertionError: assertion failed: 1.6 != 1.5999999999999999 scala> val x = NumericRange.inclusive(0.0, 1.0, 0.1)(scala.math.Numeric.DoubleAsIfIntegral) x: scala.collection.immutable.NumericRange.Inclusive[Double] = NumericRange 0.0 to 1.0 by 0.1 scala> x.drop(3).take(3).toList res3: List[Double] = List(0.30000000000000004, 0.4) ``` When encountering Double or Float, this internally uses BigDecimal, which can add numbers without losing precision. This will produce range iterator that looks like `List(1.0, 1.2, 1.4, 1.6, 1.8, 2.0)` when converted into List, as opposed to `List(1.0, 1.2, 1.4, 1.5999999999999999, 1.7999999999999998, 1.9999999999999998)`. This also fixes count when there's a stub.

Fixes scala/bug#10781 At the basis of range is an assumption that summation works reliably. Unfortunately it is not true for IEEE floating point number where numbers are stored as approximate fraction of binary numbers. Natually, Double and Float ranges are completely broken. See numbers of issues such as scala/bug#8518, scala/bug#9875, scala/bug#9874, scala/bug#8620, scala/bug#8670, and scala/bug#10759. I've attempted to fix the Double range in scala/collection-strawman#489 by faking it further using BigDecimal, but ultimately I was not able to overcome the fact that IEEE floats are not suited for ranges. This removes both Float and Double ranges, as well as the fake `Integral[T]` instances that underpins the ranges.

Fixes scala/bug#10781 At the basis of range is an assumption that summation works reliably. Unfortunately it is not true for IEEE floating point number where numbers are stored as approximate fraction of binary numbers. Natually, Double and Float ranges are completely broken. See numbers of issues such as scala/bug#8518, scala/bug#9875, scala/bug#9874, scala/bug#8620, scala/bug#8670, and scala/bug#10759. I've attempted to fix the Double range in scala/collection-strawman#489 by faking it further using BigDecimal, but ultimately I was not able to overcome the fact that IEEE floats are not suited for ranges. This removes both Float and Double ranges, as well as the fake `Integral[T]` instances that underpin their existence.

lrytz · 2018-05-24T07:51:33Z

scala/scala#6468

scabug added the help wanted label Apr 7, 2017

scabug added this to the Backlog milestone Apr 7, 2017

scabug assigned Ichoran Apr 7, 2017

This was referenced Apr 7, 2017

Floating point ranges don't work #8620

Closed

NumericRange[Double].contains() doesn't work due to rounding errors #9874

Closed

NumericRange[Double].foreach() doesn't match apply(idx) due to floating point rounding #9875

Closed

SethTisue added the library:collections label Feb 17, 2018

SethTisue unassigned Ichoran Feb 17, 2018

eed3si9n mentioned this issue Mar 3, 2018

Fix NumericRange[Double] scala/collection-strawman#489

Closed

eed3si9n mentioned this issue Mar 15, 2018

Remove Float range and Double range #10781

Closed

eed3si9n mentioned this issue Mar 25, 2018

bug#10781. Remove Float range and Double range [ci: last-only] scala/scala#6468

Merged

lrytz closed this as completed May 24, 2018

SethTisue modified the milestones: Backlog, 2.13.0-M5 May 25, 2018

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

NumericRange[Double] take and drop are broken #8518

NumericRange[Double] take and drop are broken #8518

scabug commented Apr 18, 2014

scabug commented Apr 18, 2014

scabug commented Apr 21, 2014

scabug commented Apr 25, 2014

lrytz commented May 24, 2018

NumericRange[Double] take and drop are broken #8518

NumericRange[Double] take and drop are broken #8518

Comments

scabug commented Apr 18, 2014

scabug commented Apr 18, 2014

scabug commented Apr 21, 2014

scabug commented Apr 25, 2014

lrytz commented May 24, 2018