1 {-# LANGUAGE Safe #-}
2 {-# LANGUAGE CPP #-}
4 -----------------------------------------------------------------------------
5 -- |
6 -- Module : Data.Ratio
7 -- Copyright : (c) The University of Glasgow 2001
9 --
11 -- Stability : stable
12 -- Portability : portable
13 --
14 -- Standard functions on rational numbers
15 --
16 -----------------------------------------------------------------------------
18 module Data.Ratio
19 ( Ratio
20 , Rational
21 , (%)
22 , numerator
23 , denominator
24 , approxRational
26 ) where
28 import Prelude
31 import GHC.Real -- The basic defns for Ratio
32 #endif
34 #ifdef __HUGS__
35 import Hugs.Prelude(Ratio(..), (%), numerator, denominator)
36 #endif
38 #ifdef __NHC__
39 import Ratio (Ratio(..), (%), numerator, denominator, approxRational)
40 #else
42 -- -----------------------------------------------------------------------------
43 -- approxRational
45 -- | 'approxRational', applied to two real fractional numbers @x@ and @epsilon@,
46 -- returns the simplest rational number within @epsilon@ of @x@.
47 -- A rational number @y@ is said to be /simpler/ than another @y'@ if
48 --
49 -- * @'abs' ('numerator' y) <= 'abs' ('numerator' y')@, and
50 --
51 -- * @'denominator' y <= 'denominator' y'@.
52 --
53 -- Any real interval contains a unique simplest rational;
54 -- in particular, note that @0\/1@ is the simplest rational of all.
56 -- Implementation details: Here, for simplicity, we assume a closed rational
57 -- interval. If such an interval includes at least one whole number, then
58 -- the simplest rational is the absolutely least whole number. Otherwise,
59 -- the bounds are of the form q%1 + r%d and q%1 + r'%d', where abs r < d
60 -- and abs r' < d', and the simplest rational is q%1 + the reciprocal of
61 -- the simplest rational between d'%r' and d%r.
63 approxRational :: (RealFrac a) => a -> a -> Rational
64 approxRational rat eps = simplest (rat-eps) (rat+eps)
65 where simplest x y | y < x = simplest y x
66 | x == y = xr
67 | x > 0 = simplest' n d n' d'
68 | y < 0 = - simplest' (-n') d' (-n) d
69 | otherwise = 0 :% 1
70 where xr = toRational x
71 n = numerator xr
72 d = denominator xr
73 nd' = toRational y
74 n' = numerator nd'
75 d' = denominator nd'
77 simplest' n d n' d' -- assumes 0 < n%d < n'%d'
78 | r == 0 = q :% 1
79 | q /= q' = (q+1) :% 1
80 | otherwise = (q*n''+d'') :% n''
81 where (q,r) = quotRem n d
82 (q',r') = quotRem n' d'
83 nd'' = simplest' d' r' d r
84 n'' = numerator nd''
85 d'' = denominator nd''
86 #endif