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

[Erica Sadun]

>> On Feb 29, 2016, at 5:03 PM, Joe Groff <jgroff at apple.com <mailto: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 style
print(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.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160229/bad87d6e/attachment-0001.html>