[swift-evolution] [Proposal] Decoupling Floating Point Strides from Generic Implementations
Erica Sadun
erica at ericasadun.com
Tue Mar 1 08:45:59 CST 2016
It would still be called stride. I just call it fstride here because I needed to test and run it in current Swift.
-- E
> On Mar 1, 2016, at 12:37 AM, Charles Kissinger <crk at akkyra.com> wrote:
>
> +1 for the improved floating point algorithm. I think I would be in favor of still calling it “stride” rather than “fstride”, but I could be persuaded otherwise.
>
> There seems to be some missing text in the proposal where I’ve commented below.
>
> —CK
>
>> On Feb 29, 2016, at 5:16 PM, Erica Sadun via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>>
>>>> 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
>>
> *** What 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.
>>
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org <mailto: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/f01f6713/attachment.html>
More information about the swift-evolution
mailing list