-- |
-- Module:      Data.Mod.Word
-- Copyright:   (c) 2017-2020 Andrew Lelechenko
-- Licence:     MIT
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--
-- <https://en.wikipedia.org/wiki/Modular_arithmetic Modular arithmetic>,
-- promoting moduli to the type level, with an emphasis on performance.
-- Originally part of <https://hackage.haskell.org/package/arithmoi arithmoi> package.
--
-- This module supports only moduli, which fit into 'Word'.
-- Use (slower) "Data.Mod" to handle arbitrary-sized moduli.

{-# LANGUAGE BangPatterns               #-}
{-# LANGUAGE CPP                        #-}
{-# LANGUAGE DeriveGeneric              #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE MagicHash                  #-}
{-# LANGUAGE MultiParamTypeClasses      #-}
{-# LANGUAGE TypeApplications           #-}
{-# LANGUAGE TypeFamilies               #-}
{-# LANGUAGE TypeInType                 #-}
{-# LANGUAGE UnboxedTuples              #-}

module Data.Mod.Word
  ( Mod
  , unMod
  , invertMod
  , (^%)
  ) where

import Prelude as P hiding (even)
import Control.Exception
import Control.DeepSeq
import Data.Bits
#ifdef MIN_VERSION_semirings
import Data.Euclidean (GcdDomain(..), Euclidean(..), Field)
import Data.Ratio
import Data.Semiring (Semiring(..), Ring(..))
#endif
#ifdef MIN_VERSION_vector
import Data.Primitive (Prim)
import qualified Data.Vector.Generic         as G
import qualified Data.Vector.Generic.Mutable as M
import qualified Data.Vector.Primitive       as P
import qualified Data.Vector.Unboxed         as U
#endif
import Foreign.Storable (Storable)
import GHC.Exts
import GHC.Generics
import GHC.Integer.GMP.Internals
import GHC.Natural (Natural(..))
import GHC.TypeNats (Nat, KnownNat, natVal)

-- | This data type represents
-- <https://en.wikipedia.org/wiki/Modular_arithmetic#Integers_modulo_n integers modulo m>,
-- equipped with useful instances.
--
-- For example, 3 :: 'Mod' 10 stands for the class of integers
-- congruent to \( 3 \bmod 10 \colon \ldots {−17}, −7, 3, 13, 23 \ldots \)
--
-- >>> :set -XDataKinds
-- >>> 3 + 8 :: Mod 10 -- 3 + 8 = 11 ≡ 1 (mod 10)
-- (1 `modulo` 10)
--
-- __Warning:__ division by residue, which is not
-- <https://en.wikipedia.org/wiki/Coprime_integers coprime>
-- with the modulo, throws 'DivideByZero'.
-- Consider using 'invertMod' for non-prime moduli.
newtype Mod (m :: Nat) = Mod
  { Mod m -> Word
unMod :: Word
  -- ^ The canonical representative of the residue class,
  -- always between 0 and \( m - 1 \) inclusively.
  --
  -- >>> :set -XDataKinds
  -- >>> -1 :: Mod 10
  -- (9 `modulo` 10)
  }
#ifdef MIN_VERSION_vector
  deriving (Mod m -> Mod m -> Bool
(Mod m -> Mod m -> Bool) -> (Mod m -> Mod m -> Bool) -> Eq (Mod m)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall (m :: Nat). Mod m -> Mod m -> Bool
/= :: Mod m -> Mod m -> Bool
$c/= :: forall (m :: Nat). Mod m -> Mod m -> Bool
== :: Mod m -> Mod m -> Bool
$c== :: forall (m :: Nat). Mod m -> Mod m -> Bool
Eq, Eq (Mod m)
Eq (Mod m)
-> (Mod m -> Mod m -> Ordering)
-> (Mod m -> Mod m -> Bool)
-> (Mod m -> Mod m -> Bool)
-> (Mod m -> Mod m -> Bool)
-> (Mod m -> Mod m -> Bool)
-> (Mod m -> Mod m -> Mod m)
-> (Mod m -> Mod m -> Mod m)
-> Ord (Mod m)
Mod m -> Mod m -> Bool
Mod m -> Mod m -> Ordering
Mod m -> Mod m -> Mod m
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall (m :: Nat). Eq (Mod m)
forall (m :: Nat). Mod m -> Mod m -> Bool
forall (m :: Nat). Mod m -> Mod m -> Ordering
forall (m :: Nat). Mod m -> Mod m -> Mod m
min :: Mod m -> Mod m -> Mod m
$cmin :: forall (m :: Nat). Mod m -> Mod m -> Mod m
max :: Mod m -> Mod m -> Mod m
$cmax :: forall (m :: Nat). Mod m -> Mod m -> Mod m
>= :: Mod m -> Mod m -> Bool
$c>= :: forall (m :: Nat). Mod m -> Mod m -> Bool
> :: Mod m -> Mod m -> Bool
$c> :: forall (m :: Nat). Mod m -> Mod m -> Bool
<= :: Mod m -> Mod m -> Bool
$c<= :: forall (m :: Nat). Mod m -> Mod m -> Bool
< :: Mod m -> Mod m -> Bool
$c< :: forall (m :: Nat). Mod m -> Mod m -> Bool
compare :: Mod m -> Mod m -> Ordering
$ccompare :: forall (m :: Nat). Mod m -> Mod m -> Ordering
$cp1Ord :: forall (m :: Nat). Eq (Mod m)
Ord, (forall x. Mod m -> Rep (Mod m) x)
-> (forall x. Rep (Mod m) x -> Mod m) -> Generic (Mod m)
forall x. Rep (Mod m) x -> Mod m
forall x. Mod m -> Rep (Mod m) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall (m :: Nat) x. Rep (Mod m) x -> Mod m
forall (m :: Nat) x. Mod m -> Rep (Mod m) x
$cto :: forall (m :: Nat) x. Rep (Mod m) x -> Mod m
$cfrom :: forall (m :: Nat) x. Mod m -> Rep (Mod m) x
Generic, Ptr b -> Int -> IO (Mod m)
Ptr b -> Int -> Mod m -> IO ()
Ptr (Mod m) -> IO (Mod m)
Ptr (Mod m) -> Int -> IO (Mod m)
Ptr (Mod m) -> Int -> Mod m -> IO ()
Ptr (Mod m) -> Mod m -> IO ()
Mod m -> Int
(Mod m -> Int)
-> (Mod m -> Int)
-> (Ptr (Mod m) -> Int -> IO (Mod m))
-> (Ptr (Mod m) -> Int -> Mod m -> IO ())
-> (forall b. Ptr b -> Int -> IO (Mod m))
-> (forall b. Ptr b -> Int -> Mod m -> IO ())
-> (Ptr (Mod m) -> IO (Mod m))
-> (Ptr (Mod m) -> Mod m -> IO ())
-> Storable (Mod m)
forall b. Ptr b -> Int -> IO (Mod m)
forall b. Ptr b -> Int -> Mod m -> IO ()
forall a.
(a -> Int)
-> (a -> Int)
-> (Ptr a -> Int -> IO a)
-> (Ptr a -> Int -> a -> IO ())
-> (forall b. Ptr b -> Int -> IO a)
-> (forall b. Ptr b -> Int -> a -> IO ())
-> (Ptr a -> IO a)
-> (Ptr a -> a -> IO ())
-> Storable a
forall (m :: Nat). Ptr (Mod m) -> IO (Mod m)
forall (m :: Nat). Ptr (Mod m) -> Int -> IO (Mod m)
forall (m :: Nat). Ptr (Mod m) -> Int -> Mod m -> IO ()
forall (m :: Nat). Ptr (Mod m) -> Mod m -> IO ()
forall (m :: Nat). Mod m -> Int
forall (m :: Nat) b. Ptr b -> Int -> IO (Mod m)
forall (m :: Nat) b. Ptr b -> Int -> Mod m -> IO ()
poke :: Ptr (Mod m) -> Mod m -> IO ()
$cpoke :: forall (m :: Nat). Ptr (Mod m) -> Mod m -> IO ()
peek :: Ptr (Mod m) -> IO (Mod m)
$cpeek :: forall (m :: Nat). Ptr (Mod m) -> IO (Mod m)
pokeByteOff :: Ptr b -> Int -> Mod m -> IO ()
$cpokeByteOff :: forall (m :: Nat) b. Ptr b -> Int -> Mod m -> IO ()
peekByteOff :: Ptr b -> Int -> IO (Mod m)
$cpeekByteOff :: forall (m :: Nat) b. Ptr b -> Int -> IO (Mod m)
pokeElemOff :: Ptr (Mod m) -> Int -> Mod m -> IO ()
$cpokeElemOff :: forall (m :: Nat). Ptr (Mod m) -> Int -> Mod m -> IO ()
peekElemOff :: Ptr (Mod m) -> Int -> IO (Mod m)
$cpeekElemOff :: forall (m :: Nat). Ptr (Mod m) -> Int -> IO (Mod m)
alignment :: Mod m -> Int
$calignment :: forall (m :: Nat). Mod m -> Int
sizeOf :: Mod m -> Int
$csizeOf :: forall (m :: Nat). Mod m -> Int
Storable, Addr# -> Int# -> Mod m
Addr# -> Int# -> Int# -> Mod m -> State# s -> State# s
Addr# -> Int# -> State# s -> (# State# s, Mod m #)
Addr# -> Int# -> Mod m -> State# s -> State# s
ByteArray# -> Int# -> Mod m
MutableByteArray# s -> Int# -> State# s -> (# State# s, Mod m #)
MutableByteArray# s -> Int# -> Mod m -> State# s -> State# s
MutableByteArray# s
-> Int# -> Int# -> Mod m -> State# s -> State# s
Mod m -> Int#
(Mod m -> Int#)
-> (Mod m -> Int#)
-> (ByteArray# -> Int# -> Mod m)
-> (forall s.
    MutableByteArray# s -> Int# -> State# s -> (# State# s, Mod m #))
-> (forall s.
    MutableByteArray# s -> Int# -> Mod m -> State# s -> State# s)
-> (forall s.
    MutableByteArray# s
    -> Int# -> Int# -> Mod m -> State# s -> State# s)
-> (Addr# -> Int# -> Mod m)
-> (forall s. Addr# -> Int# -> State# s -> (# State# s, Mod m #))
-> (forall s. Addr# -> Int# -> Mod m -> State# s -> State# s)
-> (forall s.
    Addr# -> Int# -> Int# -> Mod m -> State# s -> State# s)
-> Prim (Mod m)
forall s. Addr# -> Int# -> Int# -> Mod m -> State# s -> State# s
forall s. Addr# -> Int# -> State# s -> (# State# s, Mod m #)
forall s. Addr# -> Int# -> Mod m -> State# s -> State# s
forall s.
MutableByteArray# s
-> Int# -> Int# -> Mod m -> State# s -> State# s
forall s.
MutableByteArray# s -> Int# -> State# s -> (# State# s, Mod m #)
forall s.
MutableByteArray# s -> Int# -> Mod m -> State# s -> State# s
forall a.
(a -> Int#)
-> (a -> Int#)
-> (ByteArray# -> Int# -> a)
-> (forall s.
    MutableByteArray# s -> Int# -> State# s -> (# State# s, a #))
-> (forall s.
    MutableByteArray# s -> Int# -> a -> State# s -> State# s)
-> (forall s.
    MutableByteArray# s -> Int# -> Int# -> a -> State# s -> State# s)
-> (Addr# -> Int# -> a)
-> (forall s. Addr# -> Int# -> State# s -> (# State# s, a #))
-> (forall s. Addr# -> Int# -> a -> State# s -> State# s)
-> (forall s. Addr# -> Int# -> Int# -> a -> State# s -> State# s)
-> Prim a
forall (m :: Nat). Addr# -> Int# -> Mod m
forall (m :: Nat). ByteArray# -> Int# -> Mod m
forall (m :: Nat). Mod m -> Int#
forall (m :: Nat) s.
Addr# -> Int# -> Int# -> Mod m -> State# s -> State# s
forall (m :: Nat) s.
Addr# -> Int# -> State# s -> (# State# s, Mod m #)
forall (m :: Nat) s. Addr# -> Int# -> Mod m -> State# s -> State# s
forall (m :: Nat) s.
MutableByteArray# s
-> Int# -> Int# -> Mod m -> State# s -> State# s
forall (m :: Nat) s.
MutableByteArray# s -> Int# -> State# s -> (# State# s, Mod m #)
forall (m :: Nat) s.
MutableByteArray# s -> Int# -> Mod m -> State# s -> State# s
setOffAddr# :: Addr# -> Int# -> Int# -> Mod m -> State# s -> State# s
$csetOffAddr# :: forall (m :: Nat) s.
Addr# -> Int# -> Int# -> Mod m -> State# s -> State# s
writeOffAddr# :: Addr# -> Int# -> Mod m -> State# s -> State# s
$cwriteOffAddr# :: forall (m :: Nat) s. Addr# -> Int# -> Mod m -> State# s -> State# s
readOffAddr# :: Addr# -> Int# -> State# s -> (# State# s, Mod m #)
$creadOffAddr# :: forall (m :: Nat) s.
Addr# -> Int# -> State# s -> (# State# s, Mod m #)
indexOffAddr# :: Addr# -> Int# -> Mod m
$cindexOffAddr# :: forall (m :: Nat). Addr# -> Int# -> Mod m
setByteArray# :: MutableByteArray# s
-> Int# -> Int# -> Mod m -> State# s -> State# s
$csetByteArray# :: forall (m :: Nat) s.
MutableByteArray# s
-> Int# -> Int# -> Mod m -> State# s -> State# s
writeByteArray# :: MutableByteArray# s -> Int# -> Mod m -> State# s -> State# s
$cwriteByteArray# :: forall (m :: Nat) s.
MutableByteArray# s -> Int# -> Mod m -> State# s -> State# s
readByteArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, Mod m #)
$creadByteArray# :: forall (m :: Nat) s.
MutableByteArray# s -> Int# -> State# s -> (# State# s, Mod m #)
indexByteArray# :: ByteArray# -> Int# -> Mod m
$cindexByteArray# :: forall (m :: Nat). ByteArray# -> Int# -> Mod m
alignment# :: Mod m -> Int#
$calignment# :: forall (m :: Nat). Mod m -> Int#
sizeOf# :: Mod m -> Int#
$csizeOf# :: forall (m :: Nat). Mod m -> Int#
Prim)
#else
  deriving (Eq, Ord, Generic, Storable)
#endif

instance NFData (Mod m)

instance KnownNat m => Show (Mod m) where
  show :: Mod m -> String
show Mod m
m = String
"(" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Word -> String
forall a. Show a => a -> String
show (Mod m -> Word
forall (m :: Nat). Mod m -> Word
unMod Mod m
m) String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" `modulo` " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Natural -> String
forall a. Show a => a -> String
show (Mod m -> Natural
forall (n :: Nat) (proxy :: Nat -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
m) String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")"

instance KnownNat m => Enum (Mod m) where
  succ :: Mod m -> Mod m
succ Mod m
x = if Mod m
x Mod m -> Mod m -> Bool
forall a. Eq a => a -> a -> Bool
== Mod m
forall a. Bounded a => a
maxBound then ArithException -> Mod m
forall a e. Exception e => e -> a
throw ArithException
Overflow  else (Word -> Word) -> Mod m -> Mod m
coerce (Enum Word => Word -> Word
forall a. Enum a => a -> a
succ @Word) Mod m
x
  pred :: Mod m -> Mod m
pred Mod m
x = if Mod m
x Mod m -> Mod m -> Bool
forall a. Eq a => a -> a -> Bool
== Mod m
forall a. Bounded a => a
minBound then ArithException -> Mod m
forall a e. Exception e => e -> a
throw ArithException
Underflow else (Word -> Word) -> Mod m -> Mod m
coerce (Enum Word => Word -> Word
forall a. Enum a => a -> a
pred @Word) Mod m
x

  toEnum :: Int -> Mod m
toEnum   = Int -> Mod m
forall a b. (Integral a, Num b) => a -> b
fromIntegral
  fromEnum :: Mod m -> Int
fromEnum = Word -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word -> Int) -> (Mod m -> Word) -> Mod m -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Mod m -> Word
forall (m :: Nat). Mod m -> Word
unMod

  enumFrom :: Mod m -> [Mod m]
enumFrom Mod m
x       = Mod m -> Mod m -> [Mod m]
forall a. Enum a => a -> a -> [a]
enumFromTo Mod m
x Mod m
forall a. Bounded a => a
maxBound
  enumFromThen :: Mod m -> Mod m -> [Mod m]
enumFromThen Mod m
x Mod m
y = Mod m -> Mod m -> Mod m -> [Mod m]
forall a. Enum a => a -> a -> a -> [a]
enumFromThenTo Mod m
x Mod m
y (if Mod m
y Mod m -> Mod m -> Bool
forall a. Ord a => a -> a -> Bool
>= Mod m
x then Mod m
forall a. Bounded a => a
maxBound else Mod m
forall a. Bounded a => a
minBound)

  enumFromTo :: Mod m -> Mod m -> [Mod m]
enumFromTo     = (Word -> Word -> [Word]) -> Mod m -> Mod m -> [Mod m]
coerce (Enum Word => Word -> Word -> [Word]
forall a. Enum a => a -> a -> [a]
enumFromTo     @Word)
  enumFromThenTo :: Mod m -> Mod m -> Mod m -> [Mod m]
enumFromThenTo = (Word -> Word -> Word -> [Word])
-> Mod m -> Mod m -> Mod m -> [Mod m]
coerce (Enum Word => Word -> Word -> Word -> [Word]
forall a. Enum a => a -> a -> a -> [a]
enumFromThenTo @Word)

instance KnownNat m => Bounded (Mod m) where
  minBound :: Mod m
minBound = Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod Word
0
  maxBound :: Mod m
maxBound = let mx :: Mod m
mx = Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod (Natural -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Mod m -> Natural
forall (n :: Nat) (proxy :: Nat -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx) Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
1) in Mod m
mx

#if !MIN_VERSION_base(4,12,0)
addWordC# :: Word# -> Word# -> (# Word#, Int# #)
addWordC# x# y# = (# z#, word2Int# c# #)
  where
    !(# c#, z# #) = x# `plusWord2#` y#
#endif

addMod :: Natural -> Word -> Word -> Word
addMod :: Natural -> Word -> Word -> Word
addMod (NatS# GmpLimb#
m#) (W# GmpLimb#
x#) (W# GmpLimb#
y#) =
  if Int# -> Bool
isTrue# Int#
c# Bool -> Bool -> Bool
|| Int# -> Bool
isTrue# (GmpLimb#
z# GmpLimb# -> GmpLimb# -> Int#
`geWord#` GmpLimb#
m#) then GmpLimb# -> Word
W# (GmpLimb#
z# GmpLimb# -> GmpLimb# -> GmpLimb#
`minusWord#` GmpLimb#
m#) else GmpLimb# -> Word
W# GmpLimb#
z#
  where
    !(# GmpLimb#
z#, Int#
c# #) = GmpLimb#
x# GmpLimb# -> GmpLimb# -> (# GmpLimb#, Int# #)
`addWordC#` GmpLimb#
y#
addMod NatJ#{} Word
_ Word
_ = Word
forall a. a
tooLargeModulo

subMod :: Natural -> Word -> Word -> Word
subMod :: Natural -> Word -> Word -> Word
subMod (NatS# GmpLimb#
m#) (W# GmpLimb#
x#) (W# GmpLimb#
y#) =
  if Int# -> Bool
isTrue# (GmpLimb#
x# GmpLimb# -> GmpLimb# -> Int#
`geWord#` GmpLimb#
y#) then GmpLimb# -> Word
W# GmpLimb#
z# else GmpLimb# -> Word
W# (GmpLimb#
z# GmpLimb# -> GmpLimb# -> GmpLimb#
`plusWord#` GmpLimb#
m#)
  where
    z# :: GmpLimb#
z# = GmpLimb#
x# GmpLimb# -> GmpLimb# -> GmpLimb#
`minusWord#` GmpLimb#
y#
subMod NatJ#{} Word
_ Word
_ = Word
forall a. a
tooLargeModulo

negateMod :: Natural -> Word -> Word
negateMod :: Natural -> Word -> Word
negateMod Natural
_ (W# GmpLimb#
0##) = GmpLimb# -> Word
W# GmpLimb#
0##
negateMod (NatS# GmpLimb#
m#) (W# GmpLimb#
x#) = GmpLimb# -> Word
W# (GmpLimb#
m# GmpLimb# -> GmpLimb# -> GmpLimb#
`minusWord#` GmpLimb#
x#)
negateMod NatJ#{} Word
_ = Word
forall a. a
tooLargeModulo

mulMod :: Natural -> Word -> Word -> Word
mulMod :: Natural -> Word -> Word -> Word
mulMod (NatS# GmpLimb#
m#) (W# GmpLimb#
x#) (W# GmpLimb#
y#) = GmpLimb# -> Word
W# GmpLimb#
r#
  where
    !(# GmpLimb#
z1#, GmpLimb#
z2# #) = GmpLimb# -> GmpLimb# -> (# GmpLimb#, GmpLimb# #)
timesWord2# GmpLimb#
x# GmpLimb#
y#
    !(# GmpLimb#
_, GmpLimb#
r# #) = GmpLimb# -> GmpLimb# -> GmpLimb# -> (# GmpLimb#, GmpLimb# #)
quotRemWord2# GmpLimb#
z1# GmpLimb#
z2# GmpLimb#
m#
mulMod NatJ#{} Word
_ Word
_ = Word
forall a. a
tooLargeModulo

fromIntegerMod :: Natural -> Integer -> Word
fromIntegerMod :: Natural -> Integer -> Word
fromIntegerMod (NatS# GmpLimb#
0##) !Integer
_ = ArithException -> Word
forall a e. Exception e => e -> a
throw ArithException
DivideByZero
fromIntegerMod (NatS# GmpLimb#
m#) (S# Int#
x#) =
  if Int# -> Bool
isTrue# (Int#
x# Int# -> Int# -> Int#
>=# Int#
0#)
    then GmpLimb# -> Word
W# (Int# -> GmpLimb#
int2Word# Int#
x# GmpLimb# -> GmpLimb# -> GmpLimb#
`remWord#` GmpLimb#
m#)
    else Natural -> Word -> Word
negateMod (GmpLimb# -> Natural
NatS# GmpLimb#
m#) (GmpLimb# -> Word
W# (Int# -> GmpLimb#
int2Word# (Int# -> Int#
negateInt# Int#
x#) GmpLimb# -> GmpLimb# -> GmpLimb#
`remWord#` GmpLimb#
m#))
fromIntegerMod (NatS# GmpLimb#
m#) (Jp# BigNat
x#) =
  GmpLimb# -> Word
W# (BigNat
x# BigNat -> GmpLimb# -> GmpLimb#
`remBigNatWord` GmpLimb#
m#)
fromIntegerMod (NatS# GmpLimb#
m#) (Jn# BigNat
x#) =
  Natural -> Word -> Word
negateMod (GmpLimb# -> Natural
NatS# GmpLimb#
m#) (GmpLimb# -> Word
W# (BigNat
x# BigNat -> GmpLimb# -> GmpLimb#
`remBigNatWord` GmpLimb#
m#))
fromIntegerMod NatJ#{} Integer
_ = Word
forall a. a
tooLargeModulo

#ifdef MIN_VERSION_semirings

fromNaturalMod :: Natural -> Natural -> Word
fromNaturalMod :: Natural -> Natural -> Word
fromNaturalMod (NatS# GmpLimb#
0##) !Natural
_ = ArithException -> Word
forall a e. Exception e => e -> a
throw ArithException
DivideByZero
fromNaturalMod (NatS# GmpLimb#
m#) (NatS# GmpLimb#
x#) = GmpLimb# -> Word
W# (GmpLimb#
x# GmpLimb# -> GmpLimb# -> GmpLimb#
`remWord#` GmpLimb#
m#)
fromNaturalMod (NatS# GmpLimb#
m#) (NatJ# BigNat
x#) = GmpLimb# -> Word
W# (BigNat
x# BigNat -> GmpLimb# -> GmpLimb#
`remBigNatWord` GmpLimb#
m#)
fromNaturalMod NatJ#{} Natural
_ = Word
forall a. a
tooLargeModulo

#endif

tooLargeModulo :: a
tooLargeModulo :: a
tooLargeModulo = String -> a
forall a. HasCallStack => String -> a
error String
"modulo does not fit into a machine word"

instance KnownNat m => Num (Mod m) where
  mx :: Mod m
mx@(Mod !Word
x) + :: Mod m -> Mod m -> Mod m
+ (Mod !Word
y) = Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod (Word -> Mod m) -> Word -> Mod m
forall a b. (a -> b) -> a -> b
$ Natural -> Word -> Word -> Word
addMod (Mod m -> Natural
forall (n :: Nat) (proxy :: Nat -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx) Word
x Word
y
  {-# INLINE (+) #-}
  mx :: Mod m
mx@(Mod !Word
x) - :: Mod m -> Mod m -> Mod m
- (Mod !Word
y) = Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod (Word -> Mod m) -> Word -> Mod m
forall a b. (a -> b) -> a -> b
$ Natural -> Word -> Word -> Word
subMod (Mod m -> Natural
forall (n :: Nat) (proxy :: Nat -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx) Word
x Word
y
  {-# INLINE (-) #-}
  negate :: Mod m -> Mod m
negate mx :: Mod m
mx@(Mod !Word
x) = Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod (Word -> Mod m) -> Word -> Mod m
forall a b. (a -> b) -> a -> b
$ Natural -> Word -> Word
negateMod (Mod m -> Natural
forall (n :: Nat) (proxy :: Nat -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx) Word
x
  {-# INLINE negate #-}
  mx :: Mod m
mx@(Mod !Word
x) * :: Mod m -> Mod m -> Mod m
* (Mod !Word
y) = Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod (Word -> Mod m) -> Word -> Mod m
forall a b. (a -> b) -> a -> b
$ Natural -> Word -> Word -> Word
mulMod (Mod m -> Natural
forall (n :: Nat) (proxy :: Nat -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx) Word
x Word
y
  {-# INLINE (*) #-}
  abs :: Mod m -> Mod m
abs = Mod m -> Mod m
forall a. a -> a
id
  {-# INLINE abs #-}
  signum :: Mod m -> Mod m
signum = Mod m -> Mod m -> Mod m
forall a b. a -> b -> a
const Mod m
x
    where
      x :: Mod m
x = if Mod m -> Natural
forall (n :: Nat) (proxy :: Nat -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
x Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
> Natural
1 then Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod Word
1 else Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod Word
0
  {-# INLINE signum #-}
  fromInteger :: Integer -> Mod m
fromInteger Integer
x = Mod m
mx
    where
      mx :: Mod m
mx = Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod (Word -> Mod m) -> Word -> Mod m
forall a b. (a -> b) -> a -> b
$ Natural -> Integer -> Word
fromIntegerMod (Mod m -> Natural
forall (n :: Nat) (proxy :: Nat -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx) Integer
x
  {-# INLINE fromInteger #-}

#ifdef MIN_VERSION_semirings

instance KnownNat m => Semiring (Mod m) where
  plus :: Mod m -> Mod m -> Mod m
plus  = Mod m -> Mod m -> Mod m
forall a. Num a => a -> a -> a
(+)
  {-# INLINE plus #-}
  times :: Mod m -> Mod m -> Mod m
times = Mod m -> Mod m -> Mod m
forall a. Num a => a -> a -> a
(*)
  {-# INLINE times #-}
  zero :: Mod m
zero  = Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod Word
0
  {-# INLINE zero #-}
  one :: Mod m
one   = Mod m
mx
    where
      mx :: Mod m
mx = if Mod m -> Natural
forall (n :: Nat) (proxy :: Nat -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
> Natural
1 then Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod Word
1 else Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod Word
0
  {-# INLINE one #-}
  fromNatural :: Natural -> Mod m
fromNatural Natural
x = Mod m
mx
    where
      mx :: Mod m
mx = Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod (Word -> Mod m) -> Word -> Mod m
forall a b. (a -> b) -> a -> b
$ Natural -> Natural -> Word
fromNaturalMod (Mod m -> Natural
forall (n :: Nat) (proxy :: Nat -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx) Natural
x
  {-# INLINE fromNatural #-}

instance KnownNat m => Ring (Mod m) where
  negate :: Mod m -> Mod m
negate = Mod m -> Mod m
forall a. Num a => a -> a
P.negate
  {-# INLINE negate #-}

-- | See the warning about division above.
instance KnownNat m => Fractional (Mod m) where
  fromRational :: Rational -> Mod m
fromRational Rational
r = case Rational -> Integer
forall a. Ratio a -> a
denominator Rational
r of
    Integer
1   -> Mod m
num
    Integer
den -> Mod m
num Mod m -> Mod m -> Mod m
forall a. Fractional a => a -> a -> a
/ Integer -> Mod m
forall a. Num a => Integer -> a
fromInteger Integer
den
    where
      num :: Mod m
num = Integer -> Mod m
forall a. Num a => Integer -> a
fromInteger (Rational -> Integer
forall a. Ratio a -> a
numerator Rational
r)
  {-# INLINE fromRational #-}
  recip :: Mod m -> Mod m
recip Mod m
mx = case Mod m -> Maybe (Mod m)
forall (m :: Nat). KnownNat m => Mod m -> Maybe (Mod m)
invertMod Mod m
mx of
    Maybe (Mod m)
Nothing -> ArithException -> Mod m
forall a e. Exception e => e -> a
throw ArithException
DivideByZero
    Just Mod m
y  -> Mod m
y
  {-# INLINE recip #-}

-- | See the warning about division above.
instance KnownNat m => GcdDomain (Mod m) where
  divide :: Mod m -> Mod m -> Maybe (Mod m)
divide Mod m
x Mod m
y = Mod m -> Maybe (Mod m)
forall a. a -> Maybe a
Just (Mod m
x Mod m -> Mod m -> Mod m
forall a. Fractional a => a -> a -> a
/ Mod m
y)
  gcd :: Mod m -> Mod m -> Mod m
gcd        = (Mod m -> Mod m) -> Mod m -> Mod m -> Mod m
forall a b. a -> b -> a
const ((Mod m -> Mod m) -> Mod m -> Mod m -> Mod m)
-> (Mod m -> Mod m) -> Mod m -> Mod m -> Mod m
forall a b. (a -> b) -> a -> b
$ Mod m -> Mod m -> Mod m
forall a b. a -> b -> a
const Mod m
1
  lcm :: Mod m -> Mod m -> Mod m
lcm        = (Mod m -> Mod m) -> Mod m -> Mod m -> Mod m
forall a b. a -> b -> a
const ((Mod m -> Mod m) -> Mod m -> Mod m -> Mod m)
-> (Mod m -> Mod m) -> Mod m -> Mod m -> Mod m
forall a b. (a -> b) -> a -> b
$ Mod m -> Mod m -> Mod m
forall a b. a -> b -> a
const Mod m
1
  coprime :: Mod m -> Mod m -> Bool
coprime    = (Mod m -> Bool) -> Mod m -> Mod m -> Bool
forall a b. a -> b -> a
const ((Mod m -> Bool) -> Mod m -> Mod m -> Bool)
-> (Mod m -> Bool) -> Mod m -> Mod m -> Bool
forall a b. (a -> b) -> a -> b
$ Bool -> Mod m -> Bool
forall a b. a -> b -> a
const Bool
True

-- | See the warning about division above.
instance KnownNat m => Euclidean (Mod m) where
  degree :: Mod m -> Natural
degree      = Natural -> Mod m -> Natural
forall a b. a -> b -> a
const Natural
0
  quotRem :: Mod m -> Mod m -> (Mod m, Mod m)
quotRem Mod m
x Mod m
y = (Mod m
x Mod m -> Mod m -> Mod m
forall a. Fractional a => a -> a -> a
/ Mod m
y, Mod m
0)
  quot :: Mod m -> Mod m -> Mod m
quot        = Mod m -> Mod m -> Mod m
forall a. Fractional a => a -> a -> a
(/)
  rem :: Mod m -> Mod m -> Mod m
rem         = (Mod m -> Mod m) -> Mod m -> Mod m -> Mod m
forall a b. a -> b -> a
const ((Mod m -> Mod m) -> Mod m -> Mod m -> Mod m)
-> (Mod m -> Mod m) -> Mod m -> Mod m -> Mod m
forall a b. (a -> b) -> a -> b
$ Mod m -> Mod m -> Mod m
forall a b. a -> b -> a
const Mod m
0

-- | See the warning about division above.
instance KnownNat m => Field (Mod m)

#endif

-- | If an argument is
-- <https://en.wikipedia.org/wiki/Coprime_integers coprime>
-- with the modulo, return its modular inverse.
-- Otherwise return 'Nothing'.
--
-- >>> :set -XDataKinds
-- >>> invertMod 3 :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
-- Just (7 `modulo` 10)
-- >>> invertMod 4 :: Mod 10 -- 4 and 10 are not coprime
-- Nothing
invertMod :: KnownNat m => Mod m -> Maybe (Mod m)
invertMod :: Mod m -> Maybe (Mod m)
invertMod mx :: Mod m
mx@(Mod Word
x) = case Mod m -> Natural
forall (n :: Nat) (proxy :: Nat -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx of
  NatJ#{}   -> Maybe (Mod m)
forall a. a
tooLargeModulo
  NatS# GmpLimb#
0## -> Maybe (Mod m)
forall a. Maybe a
Nothing
  NatS# GmpLimb#
m#  -> Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod (Word -> Mod m) -> Maybe Word -> Maybe (Mod m)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Word -> Word -> Maybe Word
invertModWord Word
x (GmpLimb# -> Word
W# GmpLimb#
m#)

invertModWord :: Word -> Word -> Maybe Word
invertModWord :: Word -> Word -> Maybe Word
invertModWord Word
x m :: Word
m@(W# GmpLimb#
m#)
  -- If both x and k are even, no inverse exists
  | Word -> Bool
even Word
x, Int# -> Bool
isTrue# (GmpLimb#
k# GmpLimb# -> GmpLimb# -> Int#
`gtWord#` GmpLimb#
0##) = Maybe Word
forall a. Maybe a
Nothing
  | Bool
otherwise = case Word -> Word -> Maybe Word
invertModWordOdd Word
x Word
m' of
    Maybe Word
Nothing -> Maybe Word
forall a. Maybe a
Nothing
    -- goDouble cares only about mod 2^k,
    -- so overflows and underflows in (1 - x * y) are fine
    Just Word
y -> Word -> Maybe Word
forall a. a -> Maybe a
Just (Word -> Maybe Word) -> Word -> Maybe Word
forall a b. (a -> b) -> a -> b
$ Word -> Word -> Word
goDouble Word
y (Word
1 Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
x Word -> Word -> Word
forall a. Num a => a -> a -> a
* Word
y)
  where
    k# :: GmpLimb#
k# = GmpLimb# -> GmpLimb#
ctz# GmpLimb#
m#
    m' :: Word
m' = Word
m Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`unsafeShiftR` Int# -> Int
I# (GmpLimb# -> Int#
word2Int# GmpLimb#
k#)

    xm' :: Word
xm' = Word
x Word -> Word -> Word
forall a. Num a => a -> a -> a
* Word
m'

    goDouble :: Word -> Word -> Word
    goDouble :: Word -> Word -> Word
goDouble Word
acc r :: Word
r@(W# GmpLimb#
r#)
      | Int# -> Bool
isTrue# (GmpLimb#
tz# GmpLimb# -> GmpLimb# -> Int#
`geWord#` GmpLimb#
k#)
      = Word
acc
      | Bool
otherwise
      = Word -> Word -> Word
goDouble (Word
acc Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Word
m' Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`unsafeShiftL` Int
tz) (Word
r Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
xm' Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`unsafeShiftL` Int
tz)
      where
        tz# :: GmpLimb#
tz# = GmpLimb# -> GmpLimb#
ctz# GmpLimb#
r#
        tz :: Int
tz = Int# -> Int
I# (GmpLimb# -> Int#
word2Int# GmpLimb#
tz#)

-- | Extended binary gcd.
-- The second argument must be odd.
invertModWordOdd :: Word -> Word -> Maybe Word
invertModWordOdd :: Word -> Word -> Maybe Word
invertModWordOdd Word
0 !Word
_ = Maybe Word
forall a. Maybe a
Nothing
invertModWordOdd !Word
x !Word
m = Word -> Word -> Word -> Word -> Maybe Word
go00 Word
0 Word
m Word
1 Word
x
  where
    halfMp1 :: Word
    halfMp1 :: Word
halfMp1 = Word -> Word
half Word
m Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Word
1

    -- Both s and s' may be even
    go00 :: Word -> Word -> Word -> Word -> Maybe Word
    go00 :: Word -> Word -> Word -> Word -> Maybe Word
go00 !Word
r !Word
s !Word
r' !Word
s'
      | Word -> Bool
even Word
s = let (# Word
hr, Word
hs #) = Word -> Word -> (# Word, Word #)
doHalf Word
r Word
s in Word -> Word -> Word -> Word -> Maybe Word
go00 Word
hr Word
hs Word
r' Word
s'
      | Bool
otherwise = Word -> Word -> Word -> Word -> Maybe Word
go10 Word
r Word
s Word
r' Word
s'

    -- Here s is odd, s' may be even
    go10 :: Word -> Word -> Word -> Word -> Maybe Word
    go10 :: Word -> Word -> Word -> Word -> Maybe Word
go10 !Word
r !Word
s !Word
r' !Word
s'
      | Word -> Bool
even Word
s' = let (# Word
hr', Word
hs' #) = Word -> Word -> (# Word, Word #)
doHalf Word
r' Word
s' in Word -> Word -> Word -> Word -> Maybe Word
go10 Word
r Word
s Word
hr' Word
hs'
      | Bool
otherwise = Word -> Word -> Word -> Word -> Maybe Word
go11 Word
r Word
s Word
r' Word
s'

    -- Here s may be even, s' is odd
    go01 :: Word -> Word -> Word -> Word -> Maybe Word
    go01 :: Word -> Word -> Word -> Word -> Maybe Word
go01 !Word
r !Word
s !Word
r' !Word
s'
      | Word -> Bool
even Word
s = let (# Word
hr, Word
hs #) = Word -> Word -> (# Word, Word #)
doHalf Word
r Word
s in Word -> Word -> Word -> Word -> Maybe Word
go01 Word
hr Word
hs Word
r' Word
s'
      | Bool
otherwise = Word -> Word -> Word -> Word -> Maybe Word
go11 Word
r Word
s Word
r' Word
s'

    -- Both s and s' are odd
    go11 :: Word -> Word -> Word -> Word -> Maybe Word
    go11 :: Word -> Word -> Word -> Word -> Maybe Word
go11 !Word
r !Word
s !Word
r' !Word
s' = case Word
s Word -> Word -> Ordering
forall a. Ord a => a -> a -> Ordering
`compare` Word
s' of
      Ordering
EQ -> if Word
s Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
1 then Word -> Maybe Word
forall a. a -> Maybe a
Just Word
r else Maybe Word
forall a. Maybe a
Nothing
      Ordering
LT -> let newR' :: Word
newR' = Word
r' Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
r Word -> Word -> Word
forall a. Num a => a -> a -> a
+ (Word
r Word -> Word -> Word
`ge` Word
r') Word -> Word -> Word
forall a. Num a => a -> a -> a
* Word
m in
            let newS' :: Word
newS' = Word
s' Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
s in
            let (# Word
hr', Word
hs' #) = Word -> Word -> (# Word, Word #)
doHalf Word
newR' Word
newS' in
            Word -> Word -> Word -> Word -> Maybe Word
go10 Word
r Word
s Word
hr' Word
hs'
      Ordering
GT -> let newR :: Word
newR = Word
r Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
r' Word -> Word -> Word
forall a. Num a => a -> a -> a
+ (Word
r' Word -> Word -> Word
`ge` Word
r) Word -> Word -> Word
forall a. Num a => a -> a -> a
* Word
m in
            let newS :: Word
newS = Word
s Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
s' in
            let (# Word
hr, Word
hs #) = Word -> Word -> (# Word, Word #)
doHalf Word
newR Word
newS in
            Word -> Word -> Word -> Word -> Maybe Word
go01 Word
hr Word
hs Word
r' Word
s'

    doHalf :: Word -> Word -> (# Word, Word #)
    doHalf :: Word -> Word -> (# Word, Word #)
doHalf Word
r Word
s = (# Word -> Word
half Word
r Word -> Word -> Word
forall a. Num a => a -> a -> a
+ (Word
r Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&. Word
1) Word -> Word -> Word
forall a. Num a => a -> a -> a
* Word
halfMp1, Word -> Word
half Word
s #)
    {-# INLINE doHalf #-}

-- | ge x y returns 1 is x >= y and 0 otherwise.
ge :: Word -> Word -> Word
ge :: Word -> Word -> Word
ge (W# GmpLimb#
x) (W# GmpLimb#
y) = GmpLimb# -> Word
W# (Int# -> GmpLimb#
int2Word# (GmpLimb#
x GmpLimb# -> GmpLimb# -> Int#
`geWord#` GmpLimb#
y))

even :: Word -> Bool
even :: Word -> Bool
even Word
x = (Word
x Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&. Word
1) Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
0
{-# INLINE even #-}

half :: Word -> Word
half :: Word -> Word
half Word
x = Word
x Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftR` Int
1
{-# INLINE half #-}

-- | Drop-in replacement for 'Prelude.^' with a bit better performance.
-- Negative powers are allowed, but may throw 'DivideByZero', if an argument
-- is not <https://en.wikipedia.org/wiki/Coprime_integers coprime> with the modulo.
--
-- Building with @-O@ triggers a rewrite rule 'Prelude.^' = '^%'.
--
-- >>> :set -XDataKinds
-- >>> 3 ^% 4 :: Mod 10    -- 3 ^ 4 = 81 ≡ 1 (mod 10)
-- (1 `modulo` 10)
-- >>> 3 ^% (-1) :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
-- (7 `modulo` 10)
-- >>> 4 ^% (-1) :: Mod 10 -- 4 and 10 are not coprime
-- (*** Exception: divide by zero
(^%) :: (KnownNat m, Integral a) => Mod m -> a -> Mod m
mx :: Mod m
mx@(Mod (W# GmpLimb#
x#)) ^% :: Mod m -> a -> Mod m
^% a
a = case Mod m -> Natural
forall (n :: Nat) (proxy :: Nat -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx of
  NatJ#{} -> Mod m
forall a. a
tooLargeModulo
  NatS# GmpLimb#
m#
    | a
a a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0 -> case Mod m -> Maybe (Mod m)
forall (m :: Nat). KnownNat m => Mod m -> Maybe (Mod m)
invertMod Mod m
mx of
      Maybe (Mod m)
Nothing            -> ArithException -> Mod m
forall a e. Exception e => e -> a
throw ArithException
DivideByZero
      Just (Mod (W# GmpLimb#
y#)) -> Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod (Word -> Mod m) -> Word -> Mod m
forall a b. (a -> b) -> a -> b
$ GmpLimb# -> Word
W# (GmpLimb# -> a -> GmpLimb# -> GmpLimb#
forall a. Integral a => GmpLimb# -> a -> GmpLimb# -> GmpLimb#
f GmpLimb#
y# (- a
a) GmpLimb#
1##)
    | Bool
otherwise          -> Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod (Word -> Mod m) -> Word -> Mod m
forall a b. (a -> b) -> a -> b
$ GmpLimb# -> Word
W# (GmpLimb# -> a -> GmpLimb# -> GmpLimb#
forall a. Integral a => GmpLimb# -> a -> GmpLimb# -> GmpLimb#
f GmpLimb#
x# a
a GmpLimb#
1##)
    where
      f :: Integral a => Word# -> a -> Word# -> Word#
      f :: GmpLimb# -> a -> GmpLimb# -> GmpLimb#
f GmpLimb#
_  a
0 GmpLimb#
acc# = GmpLimb#
acc#
      f GmpLimb#
b# a
e GmpLimb#
acc# = GmpLimb# -> a -> GmpLimb# -> GmpLimb#
forall a. Integral a => GmpLimb# -> a -> GmpLimb# -> GmpLimb#
f GmpLimb#
bb# (a
e a -> a -> a
forall a. Integral a => a -> a -> a
`P.quot` a
2) (if a -> Bool
forall a. Integral a => a -> Bool
odd a
e then GmpLimb#
ba# else GmpLimb#
acc#)
        where
          !(# GmpLimb#
bb1#, GmpLimb#
bb2# #) = GmpLimb# -> GmpLimb# -> (# GmpLimb#, GmpLimb# #)
timesWord2# GmpLimb#
b# GmpLimb#
b#
          !(#    GmpLimb#
_, GmpLimb#
bb#  #) = GmpLimb# -> GmpLimb# -> GmpLimb# -> (# GmpLimb#, GmpLimb# #)
quotRemWord2# GmpLimb#
bb1# GmpLimb#
bb2# GmpLimb#
m#
          !(# GmpLimb#
ba1#, GmpLimb#
ba2# #) = GmpLimb# -> GmpLimb# -> (# GmpLimb#, GmpLimb# #)
timesWord2# GmpLimb#
b# GmpLimb#
acc#
          !(#    GmpLimb#
_, GmpLimb#
ba#  #) = GmpLimb# -> GmpLimb# -> GmpLimb# -> (# GmpLimb#, GmpLimb# #)
quotRemWord2# GmpLimb#
ba1# GmpLimb#
ba2# GmpLimb#
m#
{-# INLINABLE [1] (^%) #-}

{-# SPECIALISE [1] (^%) ::
  KnownNat m => Mod m -> Integer -> Mod m,
  KnownNat m => Mod m -> Natural -> Mod m,
  KnownNat m => Mod m -> Int     -> Mod m,
  KnownNat m => Mod m -> Word    -> Mod m #-}

{-# RULES
"powMod"               forall (x :: KnownNat m => Mod m) p. x ^ p = x ^% p

"powMod/2/Integer"     forall x. x ^% (2 :: Integer) = let u = x in u*u
"powMod/3/Integer"     forall x. x ^% (3 :: Integer) = let u = x in u*u*u
"powMod/2/Int"         forall x. x ^% (2 :: Int)     = let u = x in u*u
"powMod/3/Int"         forall x. x ^% (3 :: Int)     = let u = x in u*u*u
"powMod/2/Word"        forall x. x ^% (2 :: Word)    = let u = x in u*u
"powMod/3/Word"        forall x. x ^% (3 :: Word)    = let u = x in u*u*u #-}

infixr 8 ^%

#ifdef MIN_VERSION_vector

newtype instance U.MVector s (Mod m) = MV_Mod (P.MVector s Word)
newtype instance U.Vector    (Mod m) = V_Mod  (P.Vector    Word)

instance U.Unbox (Mod m)

instance M.MVector U.MVector (Mod m) where
  {-# INLINE basicLength #-}
  {-# INLINE basicUnsafeSlice #-}
  {-# INLINE basicOverlaps #-}
  {-# INLINE basicUnsafeNew #-}
  {-# INLINE basicInitialize #-}
  {-# INLINE basicUnsafeReplicate #-}
  {-# INLINE basicUnsafeRead #-}
  {-# INLINE basicUnsafeWrite #-}
  {-# INLINE basicClear #-}
  {-# INLINE basicSet #-}
  {-# INLINE basicUnsafeCopy #-}
  {-# INLINE basicUnsafeGrow #-}
  basicLength :: MVector s (Mod m) -> Int
basicLength (MV_Mod v) = MVector s Word -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
M.basicLength MVector s Word
v
  basicUnsafeSlice :: Int -> Int -> MVector s (Mod m) -> MVector s (Mod m)
basicUnsafeSlice Int
i Int
n (MV_Mod v) = MVector s Word -> MVector s (Mod m)
forall s (m :: Nat). MVector s Word -> MVector s (Mod m)
MV_Mod (MVector s Word -> MVector s (Mod m))
-> MVector s Word -> MVector s (Mod m)
forall a b. (a -> b) -> a -> b
$ Int -> Int -> MVector s Word -> MVector s Word
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
M.basicUnsafeSlice Int
i Int
n MVector s Word
v
  basicOverlaps :: MVector s (Mod m) -> MVector s (Mod m) -> Bool
basicOverlaps (MV_Mod v1) (MV_Mod v2) = MVector s Word -> MVector s Word -> Bool
forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> v s a -> Bool
M.basicOverlaps MVector s Word
v1 MVector s Word
v2
  basicUnsafeNew :: Int -> m (MVector (PrimState m) (Mod m))
basicUnsafeNew Int
n = MVector (PrimState m) Word -> MVector (PrimState m) (Mod m)
forall s (m :: Nat). MVector s Word -> MVector s (Mod m)
MV_Mod (MVector (PrimState m) Word -> MVector (PrimState m) (Mod m))
-> m (MVector (PrimState m) Word)
-> m (MVector (PrimState m) (Mod m))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> m (MVector (PrimState m) Word)
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
Int -> m (v (PrimState m) a)
M.basicUnsafeNew Int
n
  basicInitialize :: MVector (PrimState m) (Mod m) -> m ()
basicInitialize (MV_Mod v) = MVector (PrimState m) Word -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> m ()
M.basicInitialize MVector (PrimState m) Word
v
  basicUnsafeReplicate :: Int -> Mod m -> m (MVector (PrimState m) (Mod m))
basicUnsafeReplicate Int
n Mod m
x = MVector (PrimState m) Word -> MVector (PrimState m) (Mod m)
forall s (m :: Nat). MVector s Word -> MVector s (Mod m)
MV_Mod (MVector (PrimState m) Word -> MVector (PrimState m) (Mod m))
-> m (MVector (PrimState m) Word)
-> m (MVector (PrimState m) (Mod m))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> Word -> m (MVector (PrimState m) Word)
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
Int -> a -> m (v (PrimState m) a)
M.basicUnsafeReplicate Int
n (Mod m -> Word
forall (m :: Nat). Mod m -> Word
unMod Mod m
x)
  basicUnsafeRead :: MVector (PrimState m) (Mod m) -> Int -> m (Mod m)
basicUnsafeRead (MV_Mod v) Int
i = Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod (Word -> Mod m) -> m Word -> m (Mod m)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState m) Word -> Int -> m Word
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> m a
M.basicUnsafeRead MVector (PrimState m) Word
v Int
i
  basicUnsafeWrite :: MVector (PrimState m) (Mod m) -> Int -> Mod m -> m ()
basicUnsafeWrite (MV_Mod v) Int
i Mod m
x = MVector (PrimState m) Word -> Int -> Word -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> a -> m ()
M.basicUnsafeWrite MVector (PrimState m) Word
v Int
i (Mod m -> Word
forall (m :: Nat). Mod m -> Word
unMod Mod m
x)
  basicClear :: MVector (PrimState m) (Mod m) -> m ()
basicClear (MV_Mod v) = MVector (PrimState m) Word -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> m ()
M.basicClear MVector (PrimState m) Word
v
  basicSet :: MVector (PrimState m) (Mod m) -> Mod m -> m ()
basicSet (MV_Mod v) Mod m
x = MVector (PrimState m) Word -> Word -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> a -> m ()
M.basicSet MVector (PrimState m) Word
v (Mod m -> Word
forall (m :: Nat). Mod m -> Word
unMod Mod m
x)
  basicUnsafeCopy :: MVector (PrimState m) (Mod m)
-> MVector (PrimState m) (Mod m) -> m ()
basicUnsafeCopy (MV_Mod v1) (MV_Mod v2) = MVector (PrimState m) Word -> MVector (PrimState m) Word -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> v (PrimState m) a -> m ()
M.basicUnsafeCopy MVector (PrimState m) Word
v1 MVector (PrimState m) Word
v2
  basicUnsafeMove :: MVector (PrimState m) (Mod m)
-> MVector (PrimState m) (Mod m) -> m ()
basicUnsafeMove (MV_Mod v1) (MV_Mod v2) = MVector (PrimState m) Word -> MVector (PrimState m) Word -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> v (PrimState m) a -> m ()
M.basicUnsafeMove MVector (PrimState m) Word
v1 MVector (PrimState m) Word
v2
  basicUnsafeGrow :: MVector (PrimState m) (Mod m)
-> Int -> m (MVector (PrimState m) (Mod m))
basicUnsafeGrow (MV_Mod v) Int
n = MVector (PrimState m) Word -> MVector (PrimState m) (Mod m)
forall s (m :: Nat). MVector s Word -> MVector s (Mod m)
MV_Mod (MVector (PrimState m) Word -> MVector (PrimState m) (Mod m))
-> m (MVector (PrimState m) Word)
-> m (MVector (PrimState m) (Mod m))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState m) Word -> Int -> m (MVector (PrimState m) Word)
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
M.basicUnsafeGrow MVector (PrimState m) Word
v Int
n

instance G.Vector U.Vector (Mod m) where
  {-# INLINE basicUnsafeFreeze #-}
  {-# INLINE basicUnsafeThaw #-}
  {-# INLINE basicLength #-}
  {-# INLINE basicUnsafeSlice #-}
  {-# INLINE basicUnsafeIndexM #-}
  {-# INLINE elemseq #-}
  basicUnsafeFreeze :: Mutable Vector (PrimState m) (Mod m) -> m (Vector (Mod m))
basicUnsafeFreeze (MV_Mod v) = Vector Word -> Vector (Mod m)
forall (m :: Nat). Vector Word -> Vector (Mod m)
V_Mod (Vector Word -> Vector (Mod m))
-> m (Vector Word) -> m (Vector (Mod m))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Mutable Vector (PrimState m) Word -> m (Vector Word)
forall (v :: * -> *) a (m :: * -> *).
(Vector v a, PrimMonad m) =>
Mutable v (PrimState m) a -> m (v a)
G.basicUnsafeFreeze MVector (PrimState m) Word
Mutable Vector (PrimState m) Word
v
  basicUnsafeThaw :: Vector (Mod m) -> m (Mutable Vector (PrimState m) (Mod m))
basicUnsafeThaw (V_Mod v) = MVector (PrimState m) Word -> MVector (PrimState m) (Mod m)
forall s (m :: Nat). MVector s Word -> MVector s (Mod m)
MV_Mod (MVector (PrimState m) Word -> MVector (PrimState m) (Mod m))
-> m (MVector (PrimState m) Word)
-> m (MVector (PrimState m) (Mod m))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Vector Word -> m (Mutable Vector (PrimState m) Word)
forall (v :: * -> *) a (m :: * -> *).
(Vector v a, PrimMonad m) =>
v a -> m (Mutable v (PrimState m) a)
G.basicUnsafeThaw Vector Word
v
  basicLength :: Vector (Mod m) -> Int
basicLength (V_Mod v) = Vector Word -> Int
forall (v :: * -> *) a. Vector v a => v a -> Int
G.basicLength Vector Word
v
  basicUnsafeSlice :: Int -> Int -> Vector (Mod m) -> Vector (Mod m)
basicUnsafeSlice Int
i Int
n (V_Mod v) = Vector Word -> Vector (Mod m)
forall (m :: Nat). Vector Word -> Vector (Mod m)
V_Mod (Vector Word -> Vector (Mod m)) -> Vector Word -> Vector (Mod m)
forall a b. (a -> b) -> a -> b
$ Int -> Int -> Vector Word -> Vector Word
forall (v :: * -> *) a. Vector v a => Int -> Int -> v a -> v a
G.basicUnsafeSlice Int
i Int
n Vector Word
v
  basicUnsafeIndexM :: Vector (Mod m) -> Int -> m (Mod m)
basicUnsafeIndexM (V_Mod v) Int
i = Word -> Mod m
forall (m :: Nat). Word -> Mod m
Mod (Word -> Mod m) -> m Word -> m (Mod m)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Vector Word -> Int -> m Word
forall (v :: * -> *) a (m :: * -> *).
(Vector v a, Monad m) =>
v a -> Int -> m a
G.basicUnsafeIndexM Vector Word
v Int
i
  basicUnsafeCopy :: Mutable Vector (PrimState m) (Mod m) -> Vector (Mod m) -> m ()
basicUnsafeCopy (MV_Mod mv) (V_Mod v) = Mutable Vector (PrimState m) Word -> Vector Word -> m ()
forall (v :: * -> *) a (m :: * -> *).
(Vector v a, PrimMonad m) =>
Mutable v (PrimState m) a -> v a -> m ()
G.basicUnsafeCopy MVector (PrimState m) Word
Mutable Vector (PrimState m) Word
mv Vector Word
v
  elemseq :: Vector (Mod m) -> Mod m -> b -> b
elemseq Vector (Mod m)
_ = Mod m -> b -> b
seq

#endif