{-# LANGUAGE RebindableSyntax #-}
module Number.ResidueClass where

import qualified Algebra.PrincipalIdealDomain as PID
import qualified Algebra.IntegralDomain as Integral

import NumericPrelude.Base
import NumericPrelude.Numeric hiding (recip)
import Data.Maybe.HT (toMaybe)
import Data.Maybe (fromMaybe)


add, sub :: (Integral.C a) => a -> a -> a -> a
add :: a -> a -> a -> a
add a
m a
x a
y = a -> a -> a
forall a. C a => a -> a -> a
mod (a
xa -> a -> a
forall a. C a => a -> a -> a
+a
y) a
m
sub :: a -> a -> a -> a
sub a
m a
x a
y = a -> a -> a
forall a. C a => a -> a -> a
mod (a
xa -> a -> a
forall a. C a => a -> a -> a
-a
y) a
m

neg :: (Integral.C a) => a -> a -> a
neg :: a -> a -> a
neg a
m a
x = a -> a -> a
forall a. C a => a -> a -> a
mod (-a
x) a
m

mul :: (Integral.C a) => a -> a -> a -> a
mul :: a -> a -> a -> a
mul a
m a
x a
y = a -> a -> a
forall a. C a => a -> a -> a
mod (a
xa -> a -> a
forall a. C a => a -> a -> a
*a
y) a
m


{- |
The division may be ambiguous.
In this case an arbitrary quotient is returned.

@
0/:4 * 2/:4 == 0/:4
2/:4 * 2/:4 == 0/:4
@
-}
divideMaybe :: (PID.C a) => a -> a -> a -> Maybe a
divideMaybe :: a -> a -> a -> Maybe a
divideMaybe a
m a
x a
y =
   let (a
d,(a
_,a
z)) = a -> a -> (a, (a, a))
forall a. C a => a -> a -> (a, (a, a))
extendedGCD a
m a
y
       (a
q,a
r)     = a -> a -> (a, a)
forall a. C a => a -> a -> (a, a)
divMod a
x a
d
   in  Bool -> a -> Maybe a
forall a. Bool -> a -> Maybe a
toMaybe (a -> Bool
forall a. C a => a -> Bool
isZero a
r) (a -> a -> a
forall a. C a => a -> a -> a
mod (a
qa -> a -> a
forall a. C a => a -> a -> a
*a
z) a
m)

divide :: (PID.C a) => a -> a -> a -> a
divide :: a -> a -> a -> a
divide a
m a
x a
y =
   a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"ResidueClass.divide: indivisible")
             (a -> a -> a -> Maybe a
forall a. C a => a -> a -> a -> Maybe a
divideMaybe a
m a
x a
y)

recip :: (PID.C a) => a -> a -> a
recip :: a -> a -> a
recip a
m = a -> a -> a -> a
forall a. C a => a -> a -> a -> a
divide a
m a
forall a. C a => a
one