Copyright	(c) 2017-2020 Andrew Lelechenko
License	MIT
Maintainer	Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell	Safe-Inferred
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 :: Mutable Vector s (Mod m) -> ST s (Vector (Mod m)) Source # basicUnsafeThaw :: Vector (Mod m) -> ST s (Mutable Vector s (Mod m)) Source # basicLength :: Vector (Mod m) -> Int Source # basicUnsafeSlice :: Int -> Int -> Vector (Mod m) -> Vector (Mod m) Source # basicUnsafeIndexM :: Vector (Mod m) -> Int -> Box (Mod m) Source # basicUnsafeCopy :: Mutable Vector s (Mod m) -> Vector (Mod m) -> ST s () Source # elemseq :: Vector (Mod m) -> Mod m -> b -> b Source #
MVector MVector (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods basicLength :: MVector s (Mod m) -> Int Source # basicUnsafeSlice :: Int -> Int -> MVector s (Mod m) -> MVector s (Mod m) Source # basicOverlaps :: MVector s (Mod m) -> MVector s (Mod m) -> Bool Source # basicUnsafeNew :: Int -> ST s (MVector s (Mod m)) Source # basicInitialize :: MVector s (Mod m) -> ST s () Source # basicUnsafeReplicate :: Int -> Mod m -> ST s (MVector s (Mod m)) Source # basicUnsafeRead :: MVector s (Mod m) -> Int -> ST s (Mod m) Source # basicUnsafeWrite :: MVector s (Mod m) -> Int -> Mod m -> ST s () Source # basicClear :: MVector s (Mod m) -> ST s () Source # basicSet :: MVector s (Mod m) -> Mod m -> ST s () Source # basicUnsafeCopy :: MVector s (Mod m) -> MVector s (Mod m) -> ST s () Source # basicUnsafeMove :: MVector s (Mod m) -> MVector s (Mod m) -> ST s () Source # basicUnsafeGrow :: MVector s (Mod m) -> Int -> ST s (MVector s (Mod m)) Source #
Storable (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods sizeOf :: Mod m -> Int Source # alignment :: Mod m -> Int Source # peekElemOff :: Ptr (Mod m) -> Int -> IO (Mod m) Source # pokeElemOff :: Ptr (Mod m) -> Int -> Mod m -> IO () Source # peekByteOff :: Ptr b -> Int -> IO (Mod m) Source # pokeByteOff :: Ptr b -> Int -> Mod m -> IO () Source # peek :: Ptr (Mod m) -> IO (Mod m) Source # poke :: Ptr (Mod m) -> Mod m -> IO () Source #
KnownNat m => Bounded (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods minBound :: Mod m Source # maxBound :: Mod m Source #
KnownNat m => Enum (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods succ :: Mod m -> Mod m Source # pred :: Mod m -> Mod m Source # toEnum :: Int -> Mod m Source # fromEnum :: Mod m -> Int Source # enumFrom :: Mod m -> [Mod m] Source # enumFromThen :: Mod m -> Mod m -> [Mod m] Source # enumFromTo :: Mod m -> Mod m -> [Mod m] Source # enumFromThenTo :: Mod m -> Mod m -> Mod m -> [Mod m] Source #
Generic (Mod m) Source #
Instance details Defined in Data.Mod.Word Associated Types type Rep (Mod m) :: Type -> Type Source # Methods from :: Mod m -> Rep (Mod m) x Source # to :: Rep (Mod m) x -> Mod m Source #
KnownNat m => Num (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods (+) :: Mod m -> Mod m -> Mod m Source # (-) :: Mod m -> Mod m -> Mod m Source # (*) :: Mod m -> Mod m -> Mod m Source # negate :: Mod m -> Mod m Source # abs :: Mod m -> Mod m Source # signum :: Mod m -> Mod m Source # fromInteger :: Integer -> Mod m Source #
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 Source # recip :: Mod m -> Mod m Source # fromRational :: Rational -> Mod m Source #
KnownNat m => Show (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods showsPrec :: Int -> Mod m -> ShowS Source # show :: Mod m -> String Source # showList :: [Mod m] -> ShowS Source #
NFData (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods rnf :: Mod m -> () Source #
Eq (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods (==) :: Mod m -> Mod m -> Bool Source # (/=) :: Mod m -> Mod m -> Bool Source #
Ord (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods compare :: Mod m -> Mod m -> Ordering Source # (<) :: Mod m -> Mod m -> Bool Source # (<=) :: Mod m -> Mod m -> Bool Source # (>) :: Mod m -> Mod m -> Bool Source # (>=) :: Mod m -> Mod m -> Bool Source # max :: Mod m -> Mod m -> Mod m Source # min :: Mod m -> Mod m -> Mod m Source #
Prim (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods sizeOf# :: Mod m -> Int# Source # alignment# :: Mod m -> Int# Source # indexByteArray# :: ByteArray# -> Int# -> Mod m Source # readByteArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, Mod m #) Source # writeByteArray# :: MutableByteArray# s -> Int# -> Mod m -> State# s -> State# s Source # setByteArray# :: MutableByteArray# s -> Int# -> Int# -> Mod m -> State# s -> State# s Source # indexOffAddr# :: Addr# -> Int# -> Mod m Source # readOffAddr# :: Addr# -> Int# -> State# s -> (# State# s, Mod m #) Source # writeOffAddr# :: Addr# -> Int# -> Mod m -> State# s -> State# s Source # setOffAddr# :: Addr# -> Int# -> Int# -> Mod m -> State# s -> State# s Source #
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) Source # quot :: Mod m -> Mod m -> Mod m Source # rem :: Mod m -> Mod m -> Mod m Source # degree :: Mod m -> Natural Source #
KnownNat m => Field (Mod m) Source #	See the warning about division above.
Instance details Defined in Data.Mod.Word
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) Source # gcd :: Mod m -> Mod m -> Mod m Source # lcm :: Mod m -> Mod m -> Mod m Source # coprime :: Mod m -> Mod m -> Bool Source #
KnownNat m => Ring (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods negate :: Mod m -> Mod m Source #
KnownNat m => Semiring (Mod m) Source #
Instance details Defined in Data.Mod.Word Methods plus :: Mod m -> Mod m -> Mod m Source # zero :: Mod m Source # times :: Mod m -> Mod m -> Mod m Source # one :: Mod m Source # fromNatural :: Natural -> Mod m Source #
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-43ZWLUgZYT5IC3uQn2hkX3" '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