[swift-evolution] [Proposal] Decoupling Floating Point Strides from Generic Implementations

Howard Lovatt howard.lovatt at gmail.com
Tue Mar 1 01:44:13 CST 2016


Your implementation of `fstride` is faulty, it doesn't produce the
`through` value. Suggest you change to:

public extension Double {

    public func doubleStride(through end: Double, by stride: Double) ->
LazyMapCollection<Range<Int>, Double> {

        let limit = Int(trunc((end - self) / stride))

        return (0 ... limit).lazy.map { self + Double($0) * stride }

    }

}


  -- Howard.

On 1 March 2016 at 12:16, Erica Sadun via swift-evolution <
swift-evolution at swift.org> wrote:

> On Feb 29, 2016, at 5:03 PM, Joe Groff <jgroff at apple.com> wrote:
> I agree, splitting into two proposals is a good idea.
>
> -Joe
>
> Decoupling Floating Point Strides from Generic Implementations
>
>    - Proposal: SE-00XX
>    - Author(s): Erica Sadun <http://github.com/erica>
>    - Status: TBD
>    - Review manager: TBD
>
> Swift strides create progressions along "notionally continuous
> one-dimensional values" using a series of offset values. This proposal
> replaces the Swift's generic stride implementation with seperate algorithms
> for integer strides (the current implementation) and floating point strides.
>
> This proposal was discussed on-list in the "[Discussion] stride behavior
> and a little bit of a call-back to digital numbers"
> <http://article.gmane.org/gmane.comp.lang.swift.evolution/8014>thread.
> <https://gist.github.com/erica/cf50f3dc54bb3a090933#motivation>Motivation
>
> Strideable is genericized across both integer and floating point types. A
> single implementation causes floating point strides to accumulate errors
> through repeatedly adding by intervals. Floating point types deserve
> their own floating point-aware implementation that minimizes errors.
> <https://gist.github.com/erica/cf50f3dc54bb3a090933#current-art>Current
> Art
>
> A Strideable to sequence returns the sequence of values (self, self +
> stride, self + stride + stride, ... *last*) where *last* is the last
> value in the progression that is less than end.
>
> A Strideable through sequence currently returns the sequence of values (
> self, self + stride, self + tride + stride, ... *last*) where *last* is
> the last value in the progression less than or equal to end. There is no
> guarantee that end is an element of the sequence.
>
> While floating point calls present an extremely common use-case, they use
> integer-style math that accumulates errors during execution. Consider this
> example:
>
> let ideal = [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]print(zip(Array(1.0.stride(through: 2.01, by: 0.1)), ideal).map(-))// prints [0.0, 0.0, 2.2204460492503131e-16, 2.2204460492503131e-16, // 4.4408920985006262e-16, 4.4408920985006262e-16, 4.4408920985006262e-16, // 6.6613381477509392e-16, 6.6613381477509392e-16, 8.8817841970012523e-16, // 8.8817841970012523e-16]
>
>
>    - To create an array containing values from 1.0 to 2.0, the developer
>    must add an epsilon value to the throughargument. Otherwise the stride
>    progression ends near 1.9. Increasing the argument from 2.0 to 2.01 is
>    sufficient to include the end value.
>    - The errors in the sequence increase over time. You see this as
>    errors become larger towards the end of the progress. This is an artifact
>    of the generic implementation.
>
> <https://gist.github.com/erica/cf50f3dc54bb3a090933#detail-design>Detail
> Design
>
> Under the current implementation, each floating point addition in a
> generic stride accrues errors. The following progression never reaches 2.0.
>
> print(Array(1.0.stride(through: 2.0, by: 0.1)))
> // Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9]
>
> This same issue occurs with traditional C-style for loops. This is an
> artifact of floating point math, and not the specific Swift statements:
>
> var array: [Double] = []
> for var i = 1.0; i <= 2.0; i += 0.1 {
>     array.append(i)
> }
> print("Array", array)
> // Prints Array [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9]
>
> You should not have to manually add an epsilon to force a progression to
> complete.
>
> Floating point strides are inherently dissimilar to and should not be
> genericized with integer strides. I propose separate their implementation,
> freeing them to provide their own specialized progressions, using better
> numeric methods. In doing so, floating point values are no longer tied to
> implementations that unnecessarily accrue errors or otherwise provide
> less-than-ideal solutions.
>
> The following example provides a rough pass at what this might look like
> for floating point math. I leave specific algorithm details to experts; a
> decimal number solution would be more appropriate. The fun
>
> See: RandomAscii's write-ups on all things floating point
> <https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition>
> .
>
> import Darwin
> /// A `GeneratorType` for `DoubleStrideThrough`.public struct DoubleStrideThroughGenerator : GeneratorType {
>     let start: Double
>     let end: Double
>     let stride: Double
>     var iteration: Int = 0
>     var done: Bool = false
>
>     public init(start: Double, end: Double, stride: Double) {
>         (self.start, self.end, self.stride) = (start, end, stride)
>     }
>
>     /// Advance to the next element and return it, or `nil` if no next
>     /// element exists.
>     public mutating func next() -> Double? {
>         if done {
>             return nil
>         }
>         let current = start + Double(iteration) * stride; iteration += 1
>         if signbit(current - end) == signbit(stride) { // thanks Joe Groff
>             if abs(current) > abs(end) {
>                 done = true
>                 return current
>             }
>             return nil
>         }
>         return current
>     }
> }
> public struct DoubleStrideThrough : SequenceType {
>     let start: Double
>     let end: Double
>     let stride: Double
>
>     /// Return a *generator* over the elements of this *sequence*.
>     ///
>     /// - Complexity: O(1).
>     public func generate() -> DoubleStrideThroughGenerator {
>         return DoubleStrideThroughGenerator(
>             start: start, end: end, stride: stride)
>     }
>
>     init(start: Double, end: Double, stride: Double) {
>         _precondition(stride != 0, "stride size must not be zero")
>         (self.start, self.end, self.stride) = (start, end, stride)
>     }
>
> }
> public extension Double {
>     public func fstride(
>         through end: Double, by stride: Double
>         ) -> DoubleStrideThrough {
>         return DoubleStrideThrough(
>             start: self, end: end, stride: stride)
>     }
> }
>
> This implementation reduces floating point error by limiting accumulated
> additions. It uses the current Swift 2.2 through semantics (versus the
> revised through semantics proposed under separate cover), so it never
> reaches 2.0 without adding an epsilon value.
>
> print(Array(1.0.fstride(through: 2.0, by: 0.1)))// prints [1.0, 1.1000000000000001, 1.2, 1.3, 1.3999999999999999,//         1.5, 1.6000000000000001, 1.7000000000000002, 1.8, //         1.8999999999999999]
> // versus the old styleprint(Array(1.0.stride(through: 2.0, by: 0.1)))// prints [1.0, 1.1000000000000001, 1.2000000000000002, 1.3000000000000003, //         1.4000000000000004, 1.5000000000000004, 1.6000000000000005, //         1.7000000000000006, 1.8000000000000007, 1.9000000000000008]
> print(zip(Array(1.0.stride(through: 2.0, by: 0.1)),
>           Array(1.0.fstride(through: 2.0, by: 0.1))).map(-))// prints [0.0, 0.0, 2.2204460492503131e-16, 2.2204460492503131e-16, //         4.4408920985006262e-16, 4.4408920985006262e-16, 4.4408920985006262e-16, //         4.4408920985006262e-16, 6.6613381477509392e-16, 8.8817841970012523e-16]
> let ideal = [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9]print(zip(Array(1.0.fstride(through: 2.0, by: 0.1)), ideal).map(-))print(zip(Array(1.0.stride(through: 2.0, by: 0.1)), ideal).map(-))
> // prints// [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 2.2204460492503131e-16, 0.0, 0.0]// [0.0, 0.0, 2.2204460492503131e-16, 2.2204460492503131e-16, //  4.4408920985006262e-16, 4.4408920985006262e-16, 4.4408920985006262e-16, //  6.6613381477509392e-16, 6.6613381477509392e-16, 8.8817841970012523e-16]
>
> If one were looking for a quick and dirty fix, the same kind of math used
> in this rough solution (let value = start + count * interval) could be
> adopted back into the current generic implementation.
>
> <https://gist.github.com/erica/cf50f3dc54bb3a090933#alternatives-considered>Alternatives
> Considered
> While precision math for decimal numbers would be better addressed by
> introducing a decimal type and/or warnings for at-risk floating point
> numbers, those features lie outside the scope of this proposal.
>
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160301/b3f3a412/attachment.html>


More information about the swift-evolution mailing list