Skip to content

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

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
scabug opened this issue Jul 27, 2016 · 4 comments
Closed

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

scabug opened this issue Jul 27, 2016 · 4 comments
Assignees
@eed3si9n
Labels
help wanted library:collections library
Milestone
2.13.0-M5

Comments

@scabug
Copy link

scabug commented Jul 27, 2016

NumericRange is internally implemented by means of arithmetics - causing some trouble when working with doubles:

val r = 0.0 to 1.0 by 0.1
r.indexOf(r(3))  // => 3
r.contains(r(3)) // => false

Problem is that numeric range is a collection - really bad things can happen if someone passes NumericRange where Seq is expected and contains() method is used.
@scabug
Copy link
Author

scabug commented Jul 27, 2016

Imported From: https://issues.scala-lang.org/browse/SI-9874?orig=1
Reporter: Marcin Kielar (zorba128)
Affected Versions: 2.11.8
See #8518, #8670

@scabug
Copy link
Author

scabug commented Aug 2, 2016

@SethTisue said:
I would guess that this and other floating point NumericRange tickets such as #8670, #8518, #9875, and so forth would need to be fixed together as part of a general overhaul to make this code more principled.

@scabug scabug added this to the Backlog milestone Apr 7, 2017
@scabug scabug mentioned this issue Apr 7, 2017
Closed
eed3si9n added a commit to eed3si9n/collection-strawman that referenced this issue Mar 3, 2018
@eed3si9n
Fix NumericRange[Double]
6ec935e 
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)`.
@eed3si9n eed3si9n mentioned this issue Mar 3, 2018
Closed
@eed3si9n
Copy link
Member

eed3si9n commented Mar 3, 2018

Sent a PR to collection-strawman - scala/collection-strawman#489

eed3si9n added a commit to eed3si9n/collection-strawman that referenced this issue Mar 4, 2018
@eed3si9n
Fix NumericRange[Double]
f0544cd 
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.
@SethTisue SethTisue modified the milestones: Backlog, 2.13.0-RC1 Mar 6, 2018
@eed3si9n eed3si9n mentioned this issue Mar 15, 2018
Closed
eed3si9n added a commit to eed3si9n/scala that referenced this issue Mar 25, 2018
@eed3si9n
Remove Float range and Double range
9e27fa3 
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.
eed3si9n added a commit to eed3si9n/scala that referenced this issue Mar 25, 2018
@eed3si9n
Remove Float range and Double range
d839c74 
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.
@eed3si9n eed3si9n mentioned this issue Mar 25, 2018
Merged
eed3si9n added a commit to eed3si9n/scala that referenced this issue Mar 31, 2018
@eed3si9n
Remove Float range and Double range
c883a7f 
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.
eed3si9n added a commit to eed3si9n/scala that referenced this issue Apr 5, 2018
@eed3si9n
Remove Float range and Double range
ca35ada 
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.
eed3si9n added a commit to eed3si9n/scala that referenced this issue Apr 12, 2018
@eed3si9n
Remove Float range and Double range
1f0f608 
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.
eed3si9n added a commit to eed3si9n/scala that referenced this issue Apr 12, 2018
@eed3si9n
Remove Float range and Double range
485b2b2 
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.
eed3si9n added a commit to eed3si9n/scala that referenced this issue Apr 12, 2018
@eed3si9n
Remove Float range and Double range
e41fae8 
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.
eed3si9n added a commit to eed3si9n/scala that referenced this issue Apr 26, 2018
@eed3si9n
Remove Float range and Double range
feca33c 
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.
eed3si9n added a commit to eed3si9n/scala that referenced this issue May 4, 2018
@eed3si9n
Remove Float range and Double range
7db5bcc 
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.
eed3si9n added a commit to eed3si9n/scala that referenced this issue May 4, 2018
@eed3si9n
Remove Float range and Double range
16f58a1 
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 lrytz modified the milestones: 2.13.0-RC1, Backlog May 24, 2018
@lrytz lrytz closed this as completed May 24, 2018
@lrytz
Copy link
Member

lrytz commented May 24, 2018

scala/scala#6468

@SethTisue SethTisue modified the milestones: Backlog, 2.13.0-M5 May 25, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@eed3si9n eed3si9n

Labels
help wanted library:collections library
Projects
None yet
Milestone
2.13.0-M5
Development

No branches or pull requests
4 participants
@lrytz @SethTisue @eed3si9n @scabug