[Haskell-cafe] Directed rounding in haskell ?
Barak A. Pearlmutter
barak at cs.nuim.ie
Wed Apr 16 15:24:27 UTC 2014
One issue that arises with rounding modes in a pure lazy language like
Haskell is that it's pretty hard to nail down the semantics. The "round
towards negative infinity" mode is a dynamic hardware feature, available
by setting a rounding mode flag in the FPU. If you execute some hunk of
code with that flag having different values, you will in general get
different results. So if you try to do this in Haskell, you have to
decide how to expose it without violating purity.
This would break things:
roundWith :: RoundMode -> ( () -> a) -> a
consider
let x = 0.1 + 0.2 in roundWith NegInfty (\_ -> x)
vs
roundWith NegInfty (\_ -> 0.1 + 0.2)
So you need to make different numeric types. This is what Ed Kmett's
"rounding" cabal package does, albeit in a much more general way where
the new floating types are parameterized by both rounding mode and
precision.
The bottom line is that IEEE Floating Point numbers are actually a
monad. There is NaN, which makes them a Maybe, or given that there are
many NaNs perhaps an Either. And there is the rounding mode, which is
sort of a Reader.
As an aside, changing the rounding mode flags can be surprisingly slow
on modern CPUs. One trick for doing interval arithmetic efficiently is
to set the flags once, say to TowardInf. Then
x*y
computes the product of x and y rounding towards positive infinity while
-((-x)*y)
computes the same product rounding towards negative infinity without
fiddling with the rounding mode. So for adding intervals, instead of
Interval x0 x1 + Interval y0 y1 = Interval (x0+y0) (x1+y1)
Interval x0 x1 * Interval y0 y1
| x0 >= 0 && y0 >= 0
= Interval (x0*y0) (x1*y1)
-- etc
but with some added hair to fiddle with the rounding modes, one leaves
the rounding mode fixed and writes
Interval x0 x1 + Interval y0 y1 = Interval (-(-x0-y0)) (x1+y1)
Interval x0 x1 * Interval y0 y1
| x0 >= 0 && y0 >= 0
= Interval (-((-x0)*y0)) (x1*y1)
-- etc
As a final throwaway, allowing (Interval x0 x1) where x0>x1, i.e.,
improper intervals, gives a very pleasant system with a surprisingly
nice and rich semantics. For example,
Interval 1 2 - Interval 2 1 = Interval 0 0
which makes for a group rather than just a semigroup. The system is
known variously as modal intervals, Kaucher intervals, directed interval
arithmetic, or generalized interval arithmetic, and can be used to
automatically prove interesting arithmetic properties full of ∀s and ∃s.
--
Barak A. Pearlmutter
Hamilton Institute & Dept Comp Sci, NUI Maynooth, Co. Kildare, Ireland
http://www.bcl.hamilton.ie/~barak/
More information about the Haskell-Cafe
mailing list