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.

0 Comments:

Post a Comment

<< Home