List comprehensions with float iterator in F#

Question

Consider the following code:

let dl = 9.5 / 11.
let min = 21.5 + dl
let max = 40.5 - dl

let a = [ for z in min .. dl .. max -> z ] // should have 21 elements
let b = a.Length

"a" should have 21 elements but has got only 20 elements. The "max - dl" value is missing. I understand that float numbers are not precise, but I hoped that F# could work with that. If not then why F# supports List comprehensions with float iterator? To me, it is a source of bugs.

Online trial: http://tryfs.net/snippets/snippet-3H

Answer 1

Converting to decimals and looking at the numbers, it seems the 21st item would 'overshoot' max:

let dl = 9.5m / 11.m
let min = 21.5m + dl
let max = 40.5m - dl

let a = [ for z in min .. dl .. max -> z ] // should have 21 elements
let b = a.Length

let lastelement = List.nth a 19
let onemore = lastelement + dl
let overshoot = onemore - max

That is probably due to lack of precision in let dl = 9.5m / 11.m?

To get rid of this compounding error, you'll have to use another number system, i.e. Rational. F# Powerpack comes with a BigRational class that can be used like so:

let dl = 95N / 110N
let min = 215N / 10N + dl
let max = 405N / 10N - dl

let a = [ for z in min .. dl .. max -> z ] // Has 21 elements
let b = a.Length

Answer 2

I suspect the problem is with the precision of floating point values. F# adds dl to the current value each time and checks if current <= max. Because of precision problems, it might jump over max and then check if max+ε <= max (which will yield false). And so the result will have only 20 items, and not 21.

Answer 3

After running your code, if you do:

> compare a.[19] max;; 
val it : int = -1

It means max is greater than a.[19]

If we do calculations the same way the range operator does but grouping in two different ways and then compare them:

> compare (21.5+dl+dl+dl+dl+dl+dl+dl+dl) ((21.5+dl)+(dl+dl+dl+dl+dl+dl+dl));;
val it : int = 0
> compare (21.5+dl+dl+dl+dl+dl+dl+dl+dl+dl) ((21.5+dl)+(dl+dl+dl+dl+dl+dl+dl+dl));;
val it : int = -1

In this sample you can see how adding 7 times the same value in different order results in exactly the same value but if we try it 8 times the result changes depending on the grouping.

You're doing it 20 times.

So if you use the range operator with floats you should be aware of the precision problem. But the same applies to any other calculation with floats.

Answer 4

Properly handling float precision issues can be tricky. You should not rely on float equality (that's what list comprehension implicitely does for the last element). List comprehensions on float are useful when you generate an infinite stream. In other cases, you should pay attention to the last comparison.

If you want a fixed number of elements, and include both lower and upper endpoints, I suggest you write this kind of function:

let range from to_ count =
    assert (count > 1)
    let count = count - 1
    [ for i = 0 to count do yield from + float i * (to_ - from) / float count]

range 21.5 40.5 21

When I know the last element should be included, I sometimes do:

let a = [ for z in min .. dl .. max + dl*0.5 -> z ]