base: Normalize style of approxRational
[ghc.git] / libraries / base / Data / Ratio.hs
1 {-# LANGUAGE Safe #-}
2
3 -----------------------------------------------------------------------------
4 -- |
5 -- Module : Data.Ratio
6 -- Copyright : (c) The University of Glasgow 2001
7 -- License : BSD-style (see the file libraries/base/LICENSE)
8 --
9 -- Maintainer : libraries@haskell.org
10 -- Stability : stable
11 -- Portability : portable
12 --
13 -- Standard functions on rational numbers
14 --
15 -----------------------------------------------------------------------------
16
17 module Data.Ratio
18 ( Ratio
19 , Rational
20 , (%)
21 , numerator
22 , denominator
23 , approxRational
24
25 ) where
26
27 import GHC.Real -- The basic defns for Ratio
28
29 -- -----------------------------------------------------------------------------
30 -- approxRational
31
32 -- | 'approxRational', applied to two real fractional numbers @x@ and @epsilon@,
33 -- returns the simplest rational number within @epsilon@ of @x@.
34 -- A rational number @y@ is said to be /simpler/ than another @y'@ if
35 --
36 -- * @'abs' ('numerator' y) <= 'abs' ('numerator' y')@, and
37 --
38 -- * @'denominator' y <= 'denominator' y'@.
39 --
40 -- Any real interval contains a unique simplest rational;
41 -- in particular, note that @0\/1@ is the simplest rational of all.
42
43 -- Implementation details: Here, for simplicity, we assume a closed rational
44 -- interval. If such an interval includes at least one whole number, then
45 -- the simplest rational is the absolutely least whole number. Otherwise,
46 -- the bounds are of the form q%1 + r%d and q%1 + r'%d', where abs r < d
47 -- and abs r' < d', and the simplest rational is q%1 + the reciprocal of
48 -- the simplest rational between d'%r' and d%r.
49
50 approxRational :: (RealFrac a) => a -> a -> Rational
51 approxRational rat eps =
52 simplest (rat-eps) (rat+eps)
53 where
54 simplest x y
55 | y < x = simplest y x
56 | x == y = xr
57 | x > 0 = simplest' n d n' d'
58 | y < 0 = - simplest' (-n') d' (-n) d
59 | otherwise = 0 :% 1
60 where xr = toRational x
61 n = numerator xr
62 d = denominator xr
63 nd' = toRational y
64 n' = numerator nd'
65 d' = denominator nd'
66
67 simplest' n d n' d' -- assumes 0 < n%d < n'%d'
68 | r == 0 = q :% 1
69 | q /= q' = (q+1) :% 1
70 | otherwise = (q*n''+d'') :% n''
71 where (q,r) = quotRem n d
72 (q',r') = quotRem n' d'
73 nd'' = simplest' d' r' d r
74 n'' = numerator nd''
75 d'' = denominator nd''
76