Copyright	(c) 2017-2020 Andrew Lelechenko
License	MIT
Maintainer	Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell	None
Language	Haskell2010

Data.Mod.Word

Description

Modular arithmetic, promoting moduli to the type level, with an emphasis on performance. Originally part of arithmoi package.

This module supports only moduli, which fit into Word. Use (slower) Data.Mod to handle arbitrary-sized moduli.

Synopsis

data Mod (m :: Nat)
unMod :: Mod m -> Word
invertMod :: KnownNat m => Mod m -> Maybe (Mod m)
(^%) :: (KnownNat m, Integral a) => Mod m -> a -> Mod m

Documentation

data Mod (m :: Nat) Source #

This data type represents 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 coprime with the modulo, throws DivideByZero. Consider using invertMod for non-prime moduli.

Instances

Instances details

Vector Vector (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods basicUnsafeFreeze :: PrimMonad m0 => Mutable Vector (PrimState m0) (Mod m) -> m0 (Vector (Mod m)) # basicUnsafeThaw :: PrimMonad m0 => Vector (Mod m) -> m0 (Mutable Vector (PrimState m0) (Mod m)) # basicLength :: Vector (Mod m) -> Int # basicUnsafeSlice :: Int -> Int -> Vector (Mod m) -> Vector (Mod m) # basicUnsafeIndexM :: Monad m0 => Vector (Mod m) -> Int -> m0 (Mod m) # basicUnsafeCopy :: PrimMonad m0 => Mutable Vector (PrimState m0) (Mod m) -> Vector (Mod m) -> m0 () # elemseq :: Vector (Mod m) -> Mod m -> b -> b #
MVector MVector (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods basicLength :: MVector s (Mod m) -> Int # basicUnsafeSlice :: Int -> Int -> MVector s (Mod m) -> MVector s (Mod m) # basicOverlaps :: MVector s (Mod m) -> MVector s (Mod m) -> Bool # basicUnsafeNew :: PrimMonad m0 => Int -> m0 (MVector (PrimState m0) (Mod m)) # basicInitialize :: PrimMonad m0 => MVector (PrimState m0) (Mod m) -> m0 () # basicUnsafeReplicate :: PrimMonad m0 => Int -> Mod m -> m0 (MVector (PrimState m0) (Mod m)) # basicUnsafeRead :: PrimMonad m0 => MVector (PrimState m0) (Mod m) -> Int -> m0 (Mod m) # basicUnsafeWrite :: PrimMonad m0 => MVector (PrimState m0) (Mod m) -> Int -> Mod m -> m0 () # basicClear :: PrimMonad m0 => MVector (PrimState m0) (Mod m) -> m0 () # basicSet :: PrimMonad m0 => MVector (PrimState m0) (Mod m) -> Mod m -> m0 () # basicUnsafeCopy :: PrimMonad m0 => MVector (PrimState m0) (Mod m) -> MVector (PrimState m0) (Mod m) -> m0 () # basicUnsafeMove :: PrimMonad m0 => MVector (PrimState m0) (Mod m) -> MVector (PrimState m0) (Mod m) -> m0 () # basicUnsafeGrow :: PrimMonad m0 => MVector (PrimState m0) (Mod m) -> Int -> m0 (MVector (PrimState m0) (Mod m)) #
KnownNat m => Bounded (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods minBound :: Mod m # maxBound :: Mod m #
KnownNat m => Enum (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods succ :: Mod m -> Mod m # pred :: Mod m -> Mod m # toEnum :: Int -> Mod m # fromEnum :: Mod m -> Int # enumFrom :: Mod m -> [Mod m] # enumFromThen :: Mod m -> Mod m -> [Mod m] # enumFromTo :: Mod m -> Mod m -> [Mod m] # enumFromThenTo :: Mod m -> Mod m -> Mod m -> [Mod m] #
Eq (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods (==) :: Mod m -> Mod m -> Bool # (/=) :: Mod m -> Mod m -> Bool #
KnownNat m => Fractional (Mod m) Source #	See the warning about division above.
Instance details Defined in Data.Mod.Word Methods (/) :: Mod m -> Mod m -> Mod m # recip :: Mod m -> Mod m # fromRational :: Rational -> Mod m #
KnownNat m => Num (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods (+) :: Mod m -> Mod m -> Mod m # (-) :: Mod m -> Mod m -> Mod m # (*) :: Mod m -> Mod m -> Mod m # negate :: Mod m -> Mod m # abs :: Mod m -> Mod m # signum :: Mod m -> Mod m # fromInteger :: Integer -> Mod m #
Ord (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods compare :: 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 # max :: Mod m -> Mod m -> Mod m # min :: Mod m -> Mod m -> Mod m #
KnownNat m => Show (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods showsPrec :: Int -> Mod m -> ShowS # show :: Mod m -> String # showList :: [Mod m] -> ShowS #
Generic (Mod m) Source #
Instance details Defined in Data.Mod.Word Associated Types type Rep (Mod m) :: Type -> Type # Methods from :: Mod m -> Rep (Mod m) x # to :: Rep (Mod m) x -> Mod m #
Storable (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods sizeOf :: Mod m -> Int # alignment :: Mod m -> Int # peekElemOff :: Ptr (Mod m) -> Int -> IO (Mod m) # pokeElemOff :: Ptr (Mod m) -> Int -> Mod m -> IO () # peekByteOff :: Ptr b -> Int -> IO (Mod m) # pokeByteOff :: Ptr b -> Int -> Mod m -> IO () # peek :: Ptr (Mod m) -> IO (Mod m) # poke :: Ptr (Mod m) -> Mod m -> IO () #
NFData (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods rnf :: Mod m -> () #
Prim (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods sizeOf# :: Mod m -> Int# # alignment# :: Mod m -> Int# # indexByteArray# :: ByteArray# -> Int# -> Mod m # readByteArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, Mod m #) # writeByteArray# :: MutableByteArray# s -> Int# -> Mod m -> State# s -> State# s # setByteArray# :: MutableByteArray# s -> Int# -> Int# -> Mod m -> State# s -> State# s # indexOffAddr# :: Addr# -> Int# -> Mod m # readOffAddr# :: Addr# -> Int# -> State# s -> (# State# s, Mod m #) # writeOffAddr# :: Addr# -> Int# -> Mod m -> State# s -> State# s # setOffAddr# :: Addr# -> Int# -> Int# -> Mod m -> State# s -> State# s #
KnownNat m => GcdDomain (Mod m) Source #	See the warning about division above.
Instance details Defined in Data.Mod.Word Methods divide :: Mod m -> Mod m -> Maybe (Mod m) # gcd :: Mod m -> Mod m -> Mod m # lcm :: Mod m -> Mod m -> Mod m # coprime :: Mod m -> Mod m -> Bool #
KnownNat m => Euclidean (Mod m) Source #	See the warning about division above.
Instance details Defined in Data.Mod.Word Methods quotRem :: Mod m -> Mod m -> (Mod m, Mod m) # quot :: Mod m -> Mod m -> Mod m # rem :: Mod m -> Mod m -> Mod m # degree :: Mod m -> Natural #
KnownNat m => Field (Mod m) Source #	See the warning about division above.
Instance details Defined in Data.Mod.Word
KnownNat m => Semiring (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods plus :: Mod m -> Mod m -> Mod m # zero :: Mod m # times :: Mod m -> Mod m -> Mod m # one :: Mod m # fromNatural :: Natural -> Mod m #
KnownNat m => Ring (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods negate :: Mod m -> Mod m #
Unbox (Mod m) Source #
Instance details Defined in Data.Mod.Word
newtype MVector s (Mod m) Source #
Instance details Defined in Data.Mod.Word newtype MVector s (Mod m) = MV_Mod (MVector s Word)
type Rep (Mod m) Source #
Instance details Defined in Data.Mod.Word type Rep (Mod m) = D1 ('MetaData "Mod" "Data.Mod.Word" "mod-0.1.2.2-GzxqXYIw9J7ElcObj6IFg5" 'True) (C1 ('MetaCons "Mod" 'PrefixI 'True) (S1 ('MetaSel ('Just "unMod") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Word)))
newtype Vector (Mod m) Source #
Instance details Defined in Data.Mod.Word newtype Vector (Mod m) = V_Mod (Vector Word)

unMod :: Mod m -> Word Source #

The canonical representative of the residue class, always between 0 and \( m - 1 \) inclusively.

>>> :set -XDataKinds
>>> -1 :: Mod 10
(9 `modulo` 10)

invertMod :: KnownNat m => Mod m -> Maybe (Mod m) Source #

If an argument is 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

(^%) :: (KnownNat m, Integral a) => Mod m -> a -> Mod m infixr 8 Source #

Drop-in replacement for ^ with a bit better performance. Negative powers are allowed, but may throw DivideByZero, if an argument is not coprime with the modulo.

Building with -O triggers a rewrite rule ^ = ^%.

>>> :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