{-# LANGUAGE Safe #-}

-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Ratio
-- Copyright   :  (c) The University of Glasgow 2001
-- License     :  BSD-style (see the file libraries/base/LICENSE)
-- 
-- Maintainer  :  libraries@haskell.org
-- Stability   :  stable
-- Portability :  portable
--
-- Standard functions on rational numbers
--
-----------------------------------------------------------------------------

module Data.Ratio
    ( Ratio
    , Rational
    , (%)
    , numerator
    , denominator
    , approxRational

  ) where

import GHC.Real         -- The basic defns for Ratio

-- -----------------------------------------------------------------------------
-- approxRational

-- | 'approxRational', applied to two real fractional numbers @x@ and @epsilon@,
-- returns the simplest rational number within @epsilon@ of @x@.
-- A rational number @y@ is said to be /simpler/ than another @y'@ if
--
-- * @'abs' ('numerator' y) <= 'abs' ('numerator' y')@, and
--
-- * @'denominator' y <= 'denominator' y'@.
--
-- Any real interval contains a unique simplest rational;
-- in particular, note that @0\/1@ is the simplest rational of all.

-- Implementation details: Here, for simplicity, we assume a closed rational
-- interval.  If such an interval includes at least one whole number, then
-- the simplest rational is the absolutely least whole number.  Otherwise,
-- the bounds are of the form q%1 + r%d and q%1 + r'%d', where abs r < d
-- and abs r' < d', and the simplest rational is q%1 + the reciprocal of
-- the simplest rational between d'%r' and d%r.

approxRational :: (RealFrac a) => a -> a -> Rational
approxRational :: a -> a -> Rational
approxRational rat :: a
rat eps :: a
eps =
    -- We convert rat and eps to rational *before* subtracting/adding since
    -- otherwise we may overflow. This was the cause of #14425.
    Rational -> Rational -> Rational
forall a. Real a => a -> a -> Rational
simplest (a -> Rational
forall a. Real a => a -> Rational
toRational a
rat Rational -> Rational -> Rational
forall a. Num a => a -> a -> a
- a -> Rational
forall a. Real a => a -> Rational
toRational a
eps) (a -> Rational
forall a. Real a => a -> Rational
toRational a
rat Rational -> Rational -> Rational
forall a. Num a => a -> a -> a
+ a -> Rational
forall a. Real a => a -> Rational
toRational a
eps)
  where
    simplest :: a -> a -> Rational
simplest x :: a
x y :: a
y
      | a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x      =  a -> a -> Rational
simplest a
y a
x
      | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y     =  Rational
xr
      | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> 0      =  Integer -> Integer -> Integer -> Integer -> Rational
forall a. Integral a => a -> a -> a -> a -> Ratio a
simplest' Integer
n Integer
d Integer
n' Integer
d'
      | a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< 0      =  - Integer -> Integer -> Integer -> Integer -> Rational
forall a. Integral a => a -> a -> a -> a -> Ratio a
simplest' (-Integer
n') Integer
d' (-Integer
n) Integer
d
      | Bool
otherwise  =  0 Integer -> Integer -> Rational
forall a. a -> a -> Ratio a
:% 1
      where xr :: Rational
xr  = a -> Rational
forall a. Real a => a -> Rational
toRational a
x
            n :: Integer
n   = Rational -> Integer
forall a. Ratio a -> a
numerator Rational
xr
            d :: Integer
d   = Rational -> Integer
forall a. Ratio a -> a
denominator Rational
xr
            nd' :: Rational
nd' = a -> Rational
forall a. Real a => a -> Rational
toRational a
y
            n' :: Integer
n'  = Rational -> Integer
forall a. Ratio a -> a
numerator Rational
nd'
            d' :: Integer
d'  = Rational -> Integer
forall a. Ratio a -> a
denominator Rational
nd'

    simplest' :: a -> a -> a -> a -> Ratio a
simplest' n :: a
n d :: a
d n' :: a
n' d' :: a
d'       -- assumes 0 < n%d < n'%d'
      | a
r a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== 0     =  a
q a -> a -> Ratio a
forall a. a -> a -> Ratio a
:% 1
      | a
q a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
q'    =  (a
qa -> a -> a
forall a. Num a => a -> a -> a
+1) a -> a -> Ratio a
forall a. a -> a -> Ratio a
:% 1
      | Bool
otherwise  =  (a
qa -> a -> a
forall a. Num a => a -> a -> a
*a
n''a -> a -> a
forall a. Num a => a -> a -> a
+a
d'') a -> a -> Ratio a
forall a. a -> a -> Ratio a
:% a
n''
      where (q :: a
q,r :: a
r)      =  a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
quotRem a
n a
d
            (q' :: a
q',r' :: a
r')    =  a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
quotRem a
n' a
d'
            nd'' :: Ratio a
nd''       =  a -> a -> a -> a -> Ratio a
simplest' a
d' a
r' a
d a
r
            n'' :: a
n''        =  Ratio a -> a
forall a. Ratio a -> a
numerator Ratio a
nd''
            d'' :: a
d''        =  Ratio a -> a
forall a. Ratio a -> a
denominator Ratio a
nd''