[project @ 2001-06-28 14:15:04 by simonmar]
[packages/pretty.git] / Data / Ratio.hs
1 -----------------------------------------------------------------------------
2 --
3 -- Module : Data.Ratio
4 -- Copyright : (c) The University of Glasgow 2001
5 -- License : BSD-style (see the file libraries/core/LICENSE)
6 --
7 -- Maintainer : libraries@haskell.org
8 -- Stability : provisional
9 -- Portability : portable
10 --
11 -- $Id: Ratio.hs,v 1.1 2001/06/28 14:15:02 simonmar Exp $
12 --
13 -- Standard functions on rational numbers
14 --
15 -----------------------------------------------------------------------------
16
17 module Data.Ratio
18 ( Ratio
19 , Rational
20 , (%) -- :: (Integral a) => a -> a -> Ratio a
21 , numerator -- :: (Integral a) => Ratio a -> a
22 , denominator -- :: (Integral a) => Ratio a -> a
23 , approxRational -- :: (RealFrac a) => a -> a -> Rational
24
25 -- Ratio instances:
26 -- (Integral a) => Eq (Ratio a)
27 -- (Integral a) => Ord (Ratio a)
28 -- (Integral a) => Num (Ratio a)
29 -- (Integral a) => Real (Ratio a)
30 -- (Integral a) => Fractional (Ratio a)
31 -- (Integral a) => RealFrac (Ratio a)
32 -- (Integral a) => Enum (Ratio a)
33 -- (Read a, Integral a) => Read (Ratio a)
34 -- (Integral a) => Show (Ratio a)
35
36 ) where
37
38 import Prelude
39
40 #ifdef __GLASGOW_HASKELL__
41 import GHC.Real -- The basic defns for Ratio
42 #endif
43
44 -- -----------------------------------------------------------------------------
45 -- approxRational
46
47 -- @approxRational@, applied to two real fractional numbers x and epsilon,
48 -- returns the simplest rational number within epsilon of x. A rational
49 -- number n%d in reduced form is said to be simpler than another n'%d' if
50 -- abs n <= abs n' && d <= d'. Any real interval contains a unique
51 -- simplest rational; here, for simplicity, we assume a closed rational
52 -- interval. If such an interval includes at least one whole number, then
53 -- the simplest rational is the absolutely least whole number. Otherwise,
54 -- the bounds are of the form q%1 + r%d and q%1 + r'%d', where abs r < d
55 -- and abs r' < d', and the simplest rational is q%1 + the reciprocal of
56 -- the simplest rational between d'%r' and d%r.
57
58 approxRational :: (RealFrac a) => a -> a -> Rational
59 approxRational rat eps = simplest (rat-eps) (rat+eps)
60 where simplest x y | y < x = simplest y x
61 | x == y = xr
62 | x > 0 = simplest' n d n' d'
63 | y < 0 = - simplest' (-n') d' (-n) d
64 | otherwise = 0 :% 1
65 where xr = toRational x
66 n = numerator xr
67 d = denominator xr
68 nd' = toRational y
69 n' = numerator nd'
70 d' = denominator nd'
71
72 simplest' n d n' d' -- assumes 0 < n%d < n'%d'
73 | r == 0 = q :% 1
74 | q /= q' = (q+1) :% 1
75 | otherwise = (q*n''+d'') :% n''
76 where (q,r) = quotRem n d
77 (q',r') = quotRem n' d'
78 nd'' = simplest' d' r' d r
79 n'' = numerator nd''
80 d'' = denominator nd''
81