<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><b class="">General numerics comments:</b></div>We’ll want internal state and computation to be Double for Float or Double, and Float80 for Float80. This confers a couple significant advantages:<br class=""><br class="">- 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.<br class=""><br class="">- 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.<br class=""><br class="">- Using Double internally for Float loops avoids catastrophic cancellation for loops that cross zero, e.g.:<br class=""><br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>for x in stride(from: Float(-200000), through: Float(1), by: Float(0.1)) {<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}<br class=""><br class="">If computed in Float, the last 20 values produced by this are:<br class=""><br class="">-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<div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">- Double is no less computationally efficient than Float on modern x86 or ARM.</div><div class=""><br class=""></div><div class="">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.<br class=""><br class=""><b class="">One specific question:</b><br class="">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?</div><div class=""><br class=""></div><div class="">Other than those notes, this approach seems perfectly workable to me.</div><div class=""><br class=""></div><div class="">– Steve</div><div class=""><br class=""><blockquote type="cite" class="">On Apr 2, 2016, at 3:26 PM, Xiaodi Wu via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:<br class=""><br class="">All righty, here's a proof-of-concept for non-error-accumulating<br class="">stride based on the swift-3-indexing-model branch. I tried to<br class="">incorporate the feedback received in the interim. Namely:<br class=""><br class="">1. Only floating point types get this slightly more computationally<br class="">intensive "new" stride; all other types get the "classic" stride. If<br class="">accepted, this new code could be appended to Stride.swift and exist<br class="">alongside current code, which doesn't need to be modified.<br class=""><br class="">2. Based on discussions about UnsafePointer, etc., it dawned on me<br class="">that what really determines whether a StrideTo<T> accumulates error<br class="">isn't T but rather T.Stride, so based on Dave's insights above we get<br class="">"new stride" if T.Stride == FloatingPoint.<br class=""><br class="">3. I need to multiply floating point values, and if I understand<br class="">correctly multiplication will be guaranteed by a revised SignedNumber<br class="">protocol; for now, I've used a _FloatingPointStrideable protocol as a<br class="">workaround. Note that Float80 doesn't conform to FloatingPoint, so it<br class="">isn't retroactively modeled to conform to _FloatingPointStrideable.<br class="">Nothing's lost for the moment because we can't use Float80 values for<br class="">"new stride" anyway, since it doesn't currently implement the isNormal<br class="">property (see below for why I use that property).<br class=""><br class="">4. I considered Dave's suggestion whether we could avoid introducing<br class="">new types, instead modifying the existing StrideToIterator and<br class="">StrideThroughIterator and relying on compiler optimization to turn<br class="">"new" stride into "classic" stride for StrideTo<Int>, etc.; however,<br class="">because the differences between "classic" stride and "new" stride<br class="">extend beyond the iterator's next() method (see below), I thought it<br class="">best to keep the floating point logic in distinct types.<br class=""><br class="">5. One difference discussed was how to handle edge cases involving<br class="">lots of iterations; I incorporated Howard's suggestions here, so<br class="">whether a stride requires more than Int.max steps is tested<br class="">upfront--as a consequence, infinite loops are impossible. I would love<br class="">it if, as Thorsten suggests, we could use BigInts, but of course<br class="">there's no such type in the stdlib and adding one would have to be<br class="">another discussion altogether.<br class=""><br class="">6. The stride increment can't be zero; for a floating point type, it<br class="">also obviously can't be infinity or NaN. I'm inclined to think that<br class="">subnormal increments should be out of the question as well, so my<br class="">proposed streamlined criterion is simply `stride.isNormal`. Comments<br class="">on this are welcome...<br class=""><br class="">Not included:<br class="">1. I know Ranges are in flux, so I've held off on extending Range with<br class="">a striding(by:) method in this proof-of-concept.<br class="">2. No attempt at the suggested stride(from:to:steps:) quite yet.<br class="">2. No tests written yet for this proof-of-concept; I noticed that<br class="">there's a stub for testing strides with bounds of type Double, but<br class="">there's a comment about things not being ready because Double conforms<br class="">to RandomIndexType--not sure what to make of that.<br class="">3. Haven't gotten around to testing performance.<br class=""><br class=""><br class="">On Wed, Mar 30, 2016 at 12:03 PM, Erica Sadun <<a href="mailto:erica@ericasadun.com" class="">erica@ericasadun.com</a>> wrote:<br class=""><blockquote type="cite" class=""><br class="">On Mar 29, 2016, at 11:26 PM, Xiaodi Wu via swift-evolution<br class=""><<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:<br class=""><br class="">On Tue, Mar 29, 2016 at 7:48 PM, Dave Abrahams <<a href="mailto:dabrahams@apple.com" class="">dabrahams@apple.com</a>> wrote:<br class=""><br class=""><br class="">on Tue Mar 29 2016, Xiaodi Wu <<a href="http://xiaodi.wu-at-gmail.com" class="">xiaodi.wu-AT-gmail.com</a>> wrote:<br class=""><br class="">Relatedly, while you're tackling this big revision:<br class=""><br class="">I've tried to play around with what it would take to write a generic<br class="">non-error-accumulating striding method, and afaict, it would be<br class="">enormously cleaner if Strideable types are guaranteed to have + and *<br class="">(well, Strideable.Stride needs *, to be more accurate),<br class=""><br class=""><br class="">That should happen automatically, since it conforms to SignedNumber,<br class="">when we get the Integer protocols updated (project currently on hold while<br class="">we land this other revision).<br class=""><br class="">since the iterator needs to be able to compute end = start + iteration<br class="">* stride.<br class=""><br class=""><br class="">Don't you need division too if you're going to do this?<br class=""><br class=""><br class="">I didn't seem to ever need division. See attached playground (which<br class="">borrows shamelessly from existing code and Erica's proposal, and which<br class="">is written in Swift 2.2 because that's what I had handy).<br class=""><br class=""><br class="">Have you considered trying to extend the `swift-3-indexing-model` branch<br class="">at the Swift repo to take the floating point approach into account? Dave A<br class="">is working on a massive overhaul of ranges (including `Countable` items<br class="">and one would presume floating point closed and open intervals as well),<br class="">and I'd love to see better implementations of, for example,<br class="">`(x..<y).striding(by:z)`<br class="">happen for Double types.<br class=""><br class="">I'd be happy to throw a proposal together based on a proof of concept,<br class="">if you had the flexibility to work on the coding.<br class=""><br class="">-- Erica<br class=""><br class=""></blockquote><span id="cid:43778070-A7A6-4B62-A5B2-2EC4607503B8"><FloatingPointStrideable.swift></span>_______________________________________________<br class="">swift-evolution mailing list<br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class="">https://lists.swift.org/mailman/listinfo/swift-evolution<br class=""></blockquote><br class=""></div></body></html>