## Friday, April 27, 2007

Fixed precision, an update So I was a bit sloppy in my last post. When doing arithmetic it was performed exactly using Rational and not truncated according to the epsilon for the type. So, for instance, computing 4/10 + 4/10 with type Fixed Eps1 would give the answer 1. While this might seem nice, it's also wrong if every operation would be performed with epsilon 1, since 4/10 would be 0, and 0+0 is 0. So I'll amend my implementation a little.
instance (Epsilon e) => Num (Fixed e) where
(+) = lift2 (+)
(-) = lift2 (-)
(*) = lift2 (*)
negate (F x) = F (negate x)
abs (F x) = F (abs x)
signum (F x) = F (signum x)
fromInteger = F . fromInteger

instance (Epsilon e) => Fractional (Fixed e) where
(/) = lift2 (/)
fromRational x = r
where r = F \$ approx x (getEps r)

lift2 :: (Epsilon e) => (Rational -> Rational -> Rational) -> Fixed e -> Fixed e
-> Fixed e
lift2 op fx@(F x) (F y) = F \$ approx (x `op` y) (getEps fx)

approx :: Rational -> Rational -> Rational
approx x eps = approxRational (x + eps/2) eps
So after each operation we add half an epsilon (so we get rounding instead of truncation) and call the magical approxRational to get the closest rational within an epsilon.