Skip to content
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.

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

[SR-6377] Using stride(from:through:by:) with Double can miss the final value #48927

Closed
swift-ci opened this issue Nov 13, 2017 · 12 comments
Closed
Assignees
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. standard library Area: Standard library umbrella

Comments

@swift-ci
Copy link
Collaborator

Previous ID SR-6377
Radar None
Original Reporter jaaabeee (JIRA User)
Type Bug
Status Resolved
Resolution Done
Environment

MacOS 10.13.1 (17B48)

Apple Swift version 4.0.2 (swiftlang-900.0.69.1 clang-900.0.38)

Xcode Version 9.2 beta (9C34b)

Additional Detail from JIRA
Votes 0
Component/s Standard Library
Labels Bug
Assignee @xwu
Priority Medium

md5: 99443caf4eaa627d3ac214b93814606a

Issue Description:

Simple example - in the stride example, the final 'max' value is never reached, although it is for the while-loop:

let min = -0.200000000000000001
let max = 1.0
let step = 0.200000000000000001
print("stride-loop")
for i in stride(from: min, through: max, by: step) {
    print(i)
}
print("\nwhile-loop")
var i = min
while i <= max {
    print(i)
    i += step
}

Results in:

stride-loop

-0.2

0.0

0.2

0.4

0.6

0.8

while-loop

-0.2

0.0

0.2

0.4

0.6

0.8

1.0

The above fails even with values such as -0.2 instead of -0.200000001.

@belkadan
Copy link
Contributor

@airspeedswift, @moiseev, any insights?

@swift-ci
Copy link
Collaborator Author

Comment by JB Parrett (JIRA)

BTW, this still fails with more rounded-off values, such as

let min = -0.2
let max = 1.0
let step = 0.2

(fails as in the stride never makes it to the max value).

@swift-ci
Copy link
Collaborator Author

Comment by JB Parrett (JIRA)

One more observation: multiply min, max, step by 10 or 100 (and divide i by that same number) and everything works as expected. Multiply them by 1 and the original behavior remains.

for i in stride(from: min*100, through: max*100, by: step*100) {
    print(i/100)
}

@moiseev
Copy link
Mannequin

moiseev mannequin commented Nov 14, 2017

https://github.com/apple/swift/blob/master/stdlib/public/core/Stride.swift.gyb#L445
`==` should be replaced with `>=`.

UPD: Oh wait... not that simple. But something there.

@moiseev
Copy link
Mannequin

moiseev mannequin commented Nov 14, 2017

See this proposal: https://github.com/apple/swift-evolution/blob/master/proposals/0050-floating-point-stride.md

It is a matter of accumulating error.
`-0.2` is not representable and is, in fact, equal to `0.20000000000000001`.

Using `print` is a little misleading here, as it is not precise enough. When you use `debugPrint`, the correctness is more obvious. The last value in `stride` is actually `0.80000000000000004`, adding `0.2` to it makes it greater than 1.

This, though, I can't explain.
(swift) 0.80000000000000004 + 0.2
// r4 : Double = 1.0

/cc @stephentyrone @xwu

@xwu
Copy link
Collaborator

xwu commented Nov 15, 2017

The result of the example provided in the OP works as expected (to a degree). To prevent accumulating error, we stride as follows (and the documentation explicitly describes the formula):

-0.2 + 0.2 * 0

-0.2 + 0.2 * 1

-0.2 + 0.2 * 2

// ...

-0.2 + 0.2 * 6 // This equals 1.0000000000000002

// ...

In some previous versions of Swift, we would stride by adding 0.2 each time, accumulating rounding error at each iteration. That was grossly unsuitable for reasons outlined in SE-0050.

Consider the following: how many iterations are there when striding by 0.2 from -0.2 through 1? We can do the math:

(1 - (-0.2)) / 0.2 // This equals 5.9999999999999991

Put another way, it is an unavoidable property of floating-point math that `a * n - a == a * (n - 1)` does not hold for all `a`, for the same reason that `a + b - b == a` does not hold for all `a`.

Update: However, we can improve the results here by using the special floating-point facility `addingProduct` (fused multiply-add) to eliminate intermediate rounding. In this particular instance, for example, we have:

(-0.2).addingProduct(0.2, 6) // This equals 1.0 exactly

I would recommend that we go ahead and use this facility to improve the predictability of floating-point stride. This was not available when I originally fixed floating-point strides, which is why we incur the intermediate rounding error at present. It would be possible to implement this on the 4.1 branch in the next few days.

Specifically, we should leave the existing implementations alone, as it is possible that there are uses out there where the `Strideable` type is not floating point but its `Stride` is floating point. But we need one more overload:

extension Strideable where Self : FloatingPoint, Self == Stride {
public static func _step(
after current: (index: Int?, value: Self),
from start: Self, by distance: Self.Stride
) -> (index: Int?, value: Self) {
if let i = current.index {
return (i + 1, start.addingProduct(Stride(i + 1), distance))
}
// If current.index == nil, either we're just starting out (in which case
// the next index is 1), or we should proceed without an index just as
// though this floating point specialization doesn't exist.
return (current.value == start ? 1 : nil,
current.value.advanced(by: distance))
}
}

Now, on the master branch, there are several ongoing changes that should probably settle down first before we do this there as well. Firstly, there's the move to get rid of `_Strideable` which isn't yet complete. Secondly, I've noticed that Max has just implemented `IntegerStrideToCollection`, `IntegerStrideThroughCollection`, `FloatingPointStrideToCollection`, and `FloatingPointStrideThroughCollection`. Since conditional conformances are about to land soon, let's wait until those are folded into `StrideTo` and `StrideThrough`–as intended–before we do more surgery in this area. We'll need a tiny bit of cleverness to figure out `count` with floating-point stride collections, but it's not difficult.

(Edit: I should mention, SE-0050 was withdrawn instead of re-submitted because the core team wished for the proposed algorithm to be implemented without new APIs such as `IntegerStrideTo` and `FloatingPointStrideTo`. This was accordingly done, and as there was no change in API, the fix was implemented without further Swift Evolution review. It's surprising to me that Max has just added the rejected types to the standard library.)

@swift-ci
Copy link
Collaborator Author

Comment by JB Parrett (JIRA)

Thanks for looking at this. One nagging question: why does the while-loop work? Using debugPrint, I can see that the final iteration results in

0.80000000000000004 + 0.20000000000000001 = 1.0

Is it just dumb floating point luck that I end up with 1.0 instead of 1.0 and change? Here is where I would have expected to see error accumulation cause a failure, but I haven't see a case where the while loop misses the final comparison in an unexpected way.

Totally understand the floating-point issues now that I see how stride works under the covers. This seems like something that should be addressed in documentation, at a minimum. A function that has unexpected results when used with certain data types should either be explicit in calling out those limitations, or shouldn't support those data types, IMHO.

My take away is that I'll only use stride with integer values going forward, to remove this uncertainty in my code.

@xwu
Copy link
Collaborator

xwu commented Nov 15, 2017

Yes, it's totally dumb luck (well, it's not actually–it's deterministic binary floating-point math, but it's an accident of how 64-bit binary floating-point values are encoded and how floating-point arithmetic approximates real numbers) that `0.80000000000000004 + 0.2 * 1` is exactly 1 but `-0.2 + 0.2 * 6` is not. You will obtain the exact same result in every language that uses IEEE binary floating-point types. But, if you try enough other values, you'll find that your `while` loop will end up behaving in a surprising way in a lot more scenarios than the current implementation of `stride(...)`. In other words, the `while` loop doesn't "work."

Binary floating-point is hard, and in order to understand how they behave you'll need to consider these issues any time you do arithmetic with them. It's not a limitation of strides at all; it's just floating-point arithmetic. But, see my revised reply above for how we can improve this situation by taking advantage of some shiny new APIs available in Swift 3/4. That said, if your application can't tolerate rounding error (for example, if you're calculating money), under no circumstances should you use binary floating point.

@moiseev
Copy link
Mannequin

moiseev mannequin commented Nov 15, 2017

@xwu in the worst case we can have a O(N) `count`. It is bad but not unprecedented.

@xwu
Copy link
Collaborator

xwu commented Nov 16, 2017

@moiseev We could, but I don't think it needs to come to that. I think we can just test one or two adjacent values for rounding error.

That said, I do wonder if floating-point stride types should conform to `Collection`. Not really because of this rounding error business and its effect on `count`, although that will require some creativity. More so because it's so trivial to exceed `Int.max` elements without specifying particularly large bounds (for example, if you try to stride by `0.ulp` from `0` to `1.ulp`)--which is awkward. That may not be a dealbreaker on its own, but it seems so superfluous given that lack of conformance doesn't seem to be hindering anyone.

Consider also that you're not permitted to conditionally conform the same type to Collection in two different ways, which will then require some acrobatics in terms of implementation since we certainly want `Stride{To|Through} : Collection where Element : BinaryInteger`. (Although, again, I have a pretty good idea of how to go about solving the problem if necessary; in brief, I'd rework your code by conditionally conforming `Stride{To|Through} : Collection where Element : Numeric` and offloading floating-point specializations to an underscored `Strideable` method in the same vein as `_step`.)

However soluble these issues may be, though, I take their existence to be a hint that perhaps we're trying to fit a square peg into a round hole.

This is all a huge tangent from the particular issue here of eliminating an intermediate rounding error, which is very much feasible, but I would like to wait until master settles down a bit with respect to `Strideable` and conditional conformances before fixing it.

@moiseev
Copy link
Mannequin

moiseev mannequin commented Nov 16, 2017

I tried the `Numeric` constraint you're talking about and failed due to the lack of `/`. I agree, let's take incremental steps forward: start with just `BinaryInteger` version (it's likely the most used one), and then see from there.

@xwu
Copy link
Collaborator

xwu commented Nov 17, 2017

No indeed, you can't do the computation in the body of that method; it must invoke another method on the `Strideable` type itself, which I would actually argue is a superior separation of concerns. I had to do this with `_step` because the core team insisted on it, but it actually makes for an elegant design.

Let's take it step by step though. I eagerly await the merging of the PR deleting `_Strideable`, after which I'll do some simplification of `Strideable` code using conditional conformances. Somewhere in there I'll fold in a fix for this particular bug.

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. standard library Area: Standard library umbrella
Projects
None yet
Development

No branches or pull requests

3 participants