Clojure

Range function accumulates minor errors when called on floating-point numbers

Details

  • Type: Defect Defect
  • Status: Closed Closed
  • Priority: Trivial Trivial
  • Resolution: Declined
  • Affects Version/s: Release 1.5
  • Fix Version/s: None
  • Component/s: None
  • Labels:
    None

Description

Due to range's incremental computation minor errors introduced by floating point arithmetic accumulate, becoming more noticeable in long ranges and causing unexpected behaviour.

Compare the output of the following:

=> (range 0.0 10.0 0.1)
(0.0 0.1 0.2 0.30000000000000004 0.4 0.5 0.6 0.7 0.7999999999999999 0.8999999999999999 0.9999999999999999 1.0999999999999999 1.2 1.3 1.4000000000000001 1.5000000000000002 1.6000000000000003 1.7000000000000004 1.8000000000000005 1.9000000000000006 2.0000000000000004 2.1000000000000005 2.2000000000000006 2.3000000000000007 2.400000000000001 2.500000000000001 2.600000000000001 2.700000000000001 2.800000000000001 2.9000000000000012 3.0000000000000013 3.1000000000000014 3.2000000000000015 3.3000000000000016 3.4000000000000017 3.5000000000000018 3.600000000000002 3.700000000000002 3.800000000000002 3.900000000000002 4.000000000000002 4.100000000000001 4.200000000000001 4.300000000000001 4.4 4.5 4.6 4.699999999999999 4.799999999999999 4.899999999999999 4.999999999999998 5.099999999999998 5.1999999999999975 5.299999999999997 5.399999999999997 5.4999999999999964 5.599999999999996 5.699999999999996 5.799999999999995 5.899999999999995 5.999999999999995 6.099999999999994 6.199999999999994 6.299999999999994 6.399999999999993 6.499999999999993 6.5999999999999925 6.699999999999992 6.799999999999992 6.8999999999999915 6.999999999999991 7.099999999999991 7.19999999999999 7.29999999999999 7.39999999999999 7.499999999999989 7.599999999999989 7.699999999999989 7.799999999999988 7.899999999999988 7.999999999999988 8.099999999999987 8.199999999999987 8.299999999999986 8.399999999999986 8.499999999999986 8.599999999999985 8.699999999999985 8.799999999999985 8.899999999999984 8.999999999999984 9.099999999999984 9.199999999999983 9.299999999999983 9.399999999999983 9.499999999999982 9.599999999999982 9.699999999999982 9.799999999999981 9.89999999999998 9.99999999999998)

=> (defn range' [start end step] (map #(+ start (* % step)) (range 0 (/ (- end start) step) 1)))
=> (range' 0.0 10.0 0.1)
(0.0 0.1 0.2 0.30000000000000004 0.4 0.5 0.6000000000000001 0.7000000000000001 0.8 0.9 1.0 1.1 1.2000000000000002 1.3 1.4000000000000001 1.5 1.6 1.7000000000000002 1.8 1.9000000000000001 2.0 2.1 2.2 2.3000000000000003 2.4000000000000004 2.5 2.6 2.7 2.8000000000000003 2.9000000000000004 3.0 3.1 3.2 3.3000000000000003 3.4000000000000004 3.5 3.6 3.7 3.8000000000000003 3.9000000000000004 4.0 4.1000000000000005 4.2 4.3 4.4 4.5 4.6000000000000005 4.7 4.800000000000001 4.9 5.0 5.1000000000000005 5.2 5.300000000000001 5.4 5.5 5.6000000000000005 5.7 5.800000000000001 5.9 6.0 6.1000000000000005 6.2 6.300000000000001 6.4 6.5 6.6000000000000005 6.7 6.800000000000001 6.9 7.0 7.1000000000000005 7.2 7.300000000000001 7.4 7.5 7.6000000000000005 7.7 7.800000000000001 7.9 8.0 8.1 8.200000000000001 8.3 8.4 8.5 8.6 8.700000000000001 8.8 8.9 9.0 9.1 9.200000000000001 9.3 9.4 9.5 9.600000000000001 9.700000000000001 9.8 9.9)

Activity

Hide
Timothy Pratley added a comment -

[and just to be clear if it is considered an error, it would be nice if range explicitly forbade it]

Show
Timothy Pratley added a comment - [and just to be clear if it is considered an error, it would be nice if range explicitly forbade it]
Hide
Timothy Pratley added a comment -

range could avoid this issue cleanly by converting floats to bigdecimals (let me know if you think this is a good idea?)

I ran into this problem recently, and have to say it was pretty ugly. This is how I avoided the issue:

(defn rangef
"Returns a sequence of n numbers from start to end inclusive."
[start end n]
(for [i (range 0 n)]
(+ start (* i (/ (- end start) (dec n))))))

Hope that helps any disillusioned float users out there, or just pass in BigDecimals to range instead of floats... I would go so far as to say using floats with range as it stands is almost always going to end in tears (or worse as Stephen describes ).

Show
Timothy Pratley added a comment - range could avoid this issue cleanly by converting floats to bigdecimals (let me know if you think this is a good idea?) I ran into this problem recently, and have to say it was pretty ugly. This is how I avoided the issue: (defn rangef "Returns a sequence of n numbers from start to end inclusive." [start end n] (for [i (range 0 n)] (+ start (* i (/ (- end start) (dec n)))))) Hope that helps any disillusioned float users out there, or just pass in BigDecimals to range instead of floats... I would go so far as to say using floats with range as it stands is almost always going to end in tears (or worse as Stephen describes ).
Hide
Stephen Nelson added a comment -

"Returns a lazy seq of nums from start (inclusive) to end (exclusive), by step"

What specifically about that wording specifically suggests that the implementation will use naive increment-and-recurse behaviour? My reading is that the function will return a lazy sequence of numbers from start to end separated by step, not separated by 'almost step'.

This implementation leads to unexpected behaviour with bounds:

=> (count (range 0 100 1))
100
=> (count (range 0 10 0.1))
101

http://www.ima.umn.edu/~arnold/455.f96/disasters.html

Show
Stephen Nelson added a comment - "Returns a lazy seq of nums from start (inclusive) to end (exclusive), by step" What specifically about that wording specifically suggests that the implementation will use naive increment-and-recurse behaviour? My reading is that the function will return a lazy sequence of numbers from start to end separated by step, not separated by 'almost step'. This implementation leads to unexpected behaviour with bounds: => (count (range 0 100 1)) 100 => (count (range 0 10 0.1)) 101 http://www.ima.umn.edu/~arnold/455.f96/disasters.html
Hide
Stuart Halloway added a comment -

Range is incremental by design, and that is how floats work. Something with the desired behavior would need to be a different fn with a different name.

Show
Stuart Halloway added a comment - Range is incremental by design, and that is how floats work. Something with the desired behavior would need to be a different fn with a different name.
Hide
Stephen Nelson added a comment -

=> (last (range 0.0 10000000.0 0.1))
9999999.98112945
=> (last (range' 0.0 10000000.0 0.1))
9999999.9

Show
Stephen Nelson added a comment - => (last (range 0.0 10000000.0 0.1)) 9999999.98112945 => (last (range' 0.0 10000000.0 0.1)) 9999999.9

People

Vote (0)
Watch (0)

Dates

  • Created:
    Updated:
    Resolved: