Gah, hit send too soon, the values should be: -1, -0.890625, -0.796875, -0.703125, -0.59375, -0.5, -0.390625, -0.296875, -0.203125, -0.09375, 0, 0.109375, 0.203125, 0.296875, 0.40625, 0.5, 0.609375, 0.703125, 0.796875, 0.90625
i.e. nearly 10% error for the values closest to zero. – Steve > On Apr 2, 2016, at 6:30 PM, Stephen Canon via swift-evolution > <swift-evolution@swift.org> wrote: > > General numerics comments: > We’ll want internal state and computation to be Double for Float or Double, > and Float80 for Float80. This confers a couple significant advantages: > > - There are useful loops with more than 2**31 steps, which means having _step > be Int is insufficient on 32-bit systems. By contrast, 2**53 steps is > indistinguishable from “infinite loop” for consumer systems (tens of days for > a loop that does no actual work). At some point, we will want to use a wider > state, but Double is sufficient for the foreseeable future, and this can be > an internal detail so it’s easy to change if/when we need to so. > > - Using Double is preferable to using Int64 because it allows us to avoid > extra Int -> FP conversions, and avoids multi-word arithmetic on 32-bit > systems. > > - Using Double internally for Float loops avoids catastrophic cancellation > for loops that cross zero, e.g.: > > for x in stride(from: Float(-200000), through: Float(1), by: > Float(0.1)) { > } > > If computed in Float, the last 20 values produced by this are: > > -0.09375, 0, 0.109375, 0.203125, 0.296875, 0.40625, 0.5, 0.609375, 0.703125, > 0.796875, 0.90625, 1, 1.109375, 1.203125, 1.296875, 1.40625, 1.5, 1.609375, > 1.703125, 1.796875, 1.90625 > > Of course, it’s still possible to construct such examples for Double, but > they require step size of such wildly disparate scale from the endpoints that > you have to loop “forever” (hours/days) before the catastrophic cancellation > becomes a significant concern. > > - Double is no less computationally efficient than Float on modern x86 or ARM. > > We should also make sure that we codegen _start + _step*_stride to a > fused-multiply add when we have hardware support (x86 Haswell and later, all > arm64, most current armv7). This eliminates the catastrophic cancellation > issue *entirely*, and is faster than a separate mul and add to boot. > > One specific question: > I don’t see any reason to enforce that stride isn’t subnormal (and good > reasons to allow it). Why did you add that restriction? > > Other than those notes, this approach seems perfectly workable to me. > > – Steve > >> On Apr 2, 2016, at 3:26 PM, Xiaodi Wu via swift-evolution >> <swift-evolution@swift.org> wrote: >> >> All righty, here's a proof-of-concept for non-error-accumulating >> stride based on the swift-3-indexing-model branch. I tried to >> incorporate the feedback received in the interim. Namely: >> >> 1. Only floating point types get this slightly more computationally >> intensive "new" stride; all other types get the "classic" stride. If >> accepted, this new code could be appended to Stride.swift and exist >> alongside current code, which doesn't need to be modified. >> >> 2. Based on discussions about UnsafePointer, etc., it dawned on me >> that what really determines whether a StrideTo<T> accumulates error >> isn't T but rather T.Stride, so based on Dave's insights above we get >> "new stride" if T.Stride == FloatingPoint. >> >> 3. I need to multiply floating point values, and if I understand >> correctly multiplication will be guaranteed by a revised SignedNumber >> protocol; for now, I've used a _FloatingPointStrideable protocol as a >> workaround. Note that Float80 doesn't conform to FloatingPoint, so it >> isn't retroactively modeled to conform to _FloatingPointStrideable. >> Nothing's lost for the moment because we can't use Float80 values for >> "new stride" anyway, since it doesn't currently implement the isNormal >> property (see below for why I use that property). >> >> 4. I considered Dave's suggestion whether we could avoid introducing >> new types, instead modifying the existing StrideToIterator and >> StrideThroughIterator and relying on compiler optimization to turn >> "new" stride into "classic" stride for StrideTo<Int>, etc.; however, >> because the differences between "classic" stride and "new" stride >> extend beyond the iterator's next() method (see below), I thought it >> best to keep the floating point logic in distinct types. >> >> 5. One difference discussed was how to handle edge cases involving >> lots of iterations; I incorporated Howard's suggestions here, so >> whether a stride requires more than Int.max steps is tested >> upfront--as a consequence, infinite loops are impossible. I would love >> it if, as Thorsten suggests, we could use BigInts, but of course >> there's no such type in the stdlib and adding one would have to be >> another discussion altogether. >> >> 6. The stride increment can't be zero; for a floating point type, it >> also obviously can't be infinity or NaN. I'm inclined to think that >> subnormal increments should be out of the question as well, so my >> proposed streamlined criterion is simply `stride.isNormal`. Comments >> on this are welcome... >> >> Not included: >> 1. I know Ranges are in flux, so I've held off on extending Range with >> a striding(by:) method in this proof-of-concept. >> 2. No attempt at the suggested stride(from:to:steps:) quite yet. >> 2. No tests written yet for this proof-of-concept; I noticed that >> there's a stub for testing strides with bounds of type Double, but >> there's a comment about things not being ready because Double conforms >> to RandomIndexType--not sure what to make of that. >> 3. Haven't gotten around to testing performance. >> >> >> On Wed, Mar 30, 2016 at 12:03 PM, Erica Sadun <er...@ericasadun.com> wrote: >>> >>> On Mar 29, 2016, at 11:26 PM, Xiaodi Wu via swift-evolution >>> <swift-evolution@swift.org> wrote: >>> >>> On Tue, Mar 29, 2016 at 7:48 PM, Dave Abrahams <dabrah...@apple.com> wrote: >>> >>> >>> on Tue Mar 29 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote: >>> >>> Relatedly, while you're tackling this big revision: >>> >>> I've tried to play around with what it would take to write a generic >>> non-error-accumulating striding method, and afaict, it would be >>> enormously cleaner if Strideable types are guaranteed to have + and * >>> (well, Strideable.Stride needs *, to be more accurate), >>> >>> >>> That should happen automatically, since it conforms to SignedNumber, >>> when we get the Integer protocols updated (project currently on hold while >>> we land this other revision). >>> >>> since the iterator needs to be able to compute end = start + iteration >>> * stride. >>> >>> >>> Don't you need division too if you're going to do this? >>> >>> >>> I didn't seem to ever need division. See attached playground (which >>> borrows shamelessly from existing code and Erica's proposal, and which >>> is written in Swift 2.2 because that's what I had handy). >>> >>> >>> Have you considered trying to extend the `swift-3-indexing-model` branch >>> at the Swift repo to take the floating point approach into account? Dave A >>> is working on a massive overhaul of ranges (including `Countable` items >>> and one would presume floating point closed and open intervals as well), >>> and I'd love to see better implementations of, for example, >>> `(x..<y).striding(by:z)` >>> happen for Double types. >>> >>> I'd be happy to throw a proposal together based on a proof of concept, >>> if you had the flexibility to work on the coding. >>> >>> -- Erica >>> >> <FloatingPointStrideable.swift>_______________________________________________ >> swift-evolution mailing list >> swift-evolution@swift.org >> https://lists.swift.org/mailman/listinfo/swift-evolution > > _______________________________________________ > swift-evolution mailing list > swift-evolution@swift.org > https://lists.swift.org/mailman/listinfo/swift-evolution _______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution