[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