[Haskell-cafe] instance Enum Double considered not entirelygreat?
Chris Smith
cdsmith at gmail.com
Tue Sep 27 05:55:40 CEST 2011
On Mon, 2011-09-26 at 19:54 -0700, Donn Cave wrote:
> Pardon the questions from the gallery, but ... I can sure see that
> 0.3 shouldn't be included in the result by overshooting the limit
> (i.e., 0.30000000000000004), and the above expectations about
> [0,2..9] are obvious enough, but now I have to ask about [0,2..8] -
> would you not expect 8 in the result? Or is it not an upper bound?
Donn,
[0, 2 .. 8] should be fine no matter the type, because integers of those
sizes are all exactly representable in all of the types involved. The
reason for the example with a step size of 0.1 is that 0.1 is actually
an infinitely repeating number in base 2 (because the denominator has a
prime factor of 5). So actually *none* of the exact real numbers 0.1,
0.2, or 0.3 are representable with floating point types. The
corresponding literals actually refer to real numbers that are slightly
off from those.
Furthermore, because the step size is not *exactly* 0.1, when it's added
repeatedly in the sequence, the result has some (very small) drift due
to repeated rounding error... just enough that by the time you get in
the vacinity of 0.3, the corresponding value in the sequence is actually
*neither* the rational number 0.3, *nor* the floating point literal 0.3.
Instead, it's one ulp larger than the floating point literal because of
that drift.
So there are two perspectives here. One is that we should think in
terms of exact values of the type Float, which means we'd want to
exclude it, because it's larger than the top end of the range. The
other is that we should think of approximate values of real numbers, in
which case it's best to pick the endpoint closest to the stated one, to
correct for what's obviously unintended drift due to rounding.
So that's what this is about: do we think of Float as an approximate
real number type, or as an exact type with specific values. If the
latter, then "of course" you exclude the value that's larger than the
upper range. If the former, then using comparison operators like '<'
implies a proof obligation that the result of the computation remains
stable (loosely speaking, the function continuous) at that boundary
despite small rounding error in either direction. In that case,
creating a language feature where, in the *normal* case of listing the
last value you expect in the list, 0.3 (as an approximate real number)
is excluded from this list just because of technicalities about the
representation is an un-useful implementation, to say the least, and
makes it far more difficult to satisfy that proof obligation.
Personally, I see floating point values as approximate real numbers.
Anything else in unrealistic: the *fact* of the matter is that no one is
reasoning about ulps or exact rational values when they use Float and
Double. In practice, even hardware implementations of some floating
point functions have indeterminate results in the exact sense. Often,
the guarantee provided by an FPU is that the result will be within one
ulp of the correct answer, which means the exact value of the answer
isn't even known! So, should we put all floating point calculations in
the IO monad because they aren't pure functions? Or can we admit that
people use floating point to approximate reals and accept the looser
reasoning?
--
Chris Smith
More information about the Haskell-Cafe
mailing list