mod-0.2.0.1: Fast type-safe modular arithmetic

Copyright | (c) 2017-2022 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 the arithmoi package.

This module supports only moduli, which fit into `Word`. Use the (slower) Data.Mod module for handling 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

Note: `Mod` 0 has no inhabitants, eventhough \( \mathbb{Z}/0\mathbb{Z} \) is technically isomorphic to \( \mathbb{Z} \).

#### Instances

Instances details

Vector Vector (Mod m) Source # | No validation checks are performed; reading untrusted data may corrupt internal invariants.

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 # | No validation checks are performed; reading untrusted data may corrupt internal invariants.

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 # | No validation checks are performed; reading untrusted data may corrupt internal invariants.

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 => Read (Mod m) Source # | Wrapping behaviour, similar to the existing `instance` `Read` `Int`.
Instance details Defined in Data.Mod.Word Methods readsPrec :: Int -> ReadS (Mod m) Source # readList :: ReadS [Mod m] Source # readPrec :: ReadPrec (Mod m) Source # readListPrec :: ReadPrec [Mod m] Source #
KnownNat m => Fractional (Mod m) Source # | Division by a residue, which is not coprime with the modulus, throws `DivideByZero`. Consider using `invertMod` for non-prime moduli.
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 => Real (Mod m) Source # |
Instance details Defined in Data.Mod.Word Methods toRational :: Mod m -> Rational Source #
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 # | No validation checks are performed; reading untrusted data may corrupt internal invariants.

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 # | `Mod` `m` is not even an integral domain for composite `m`, much less a Euclidean domain. The instance is lawful only for prime `m`, otherwise we try to do our best: ``quot` x y` returns any `z` such that `x == y * z`, `rem` is not always 0, and both can throw `DivideByZero`.
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 # | `Mod` `m` is not even an integral domain for composite `m`, much less a field. The instance is lawful only for prime `m`, otherwise division by a residue, which is not coprime with the modulus, throws `DivideByZero`. Consider using `invertMod` for non-prime moduli.
Instance details Defined in Data.Mod.Word
KnownNat m => GcdDomain (Mod m) Source # | `Mod` `m` is not even an integral domain for composite `m`, much less a GCD domain. However, `gcd` and `lcm` are still meaningful even for composite `m`, corresponding to a sum and an intersection of ideals. The instance is lawful only for prime `m`, otherwise ``divide` x y` tries to return any `Just z` such that `x == y * z`.
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 # | No validation checks are performed; reading untrusted data may corrupt internal invariants.
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.2.0.1-5CA0EgGgypkAyHMyE79OTI" '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

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

If an argument is coprime with the modulus, return its modular inverse. Otherwise return `Nothing`.

    >>> :set -XDataKinds
    >>> invertMod 3 :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
    Just 7
    >>> 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 modulus.

    >>> :set -XDataKinds
    >>> 3 ^% 4 :: Mod 10    -- 3 ^ 4 = 81 ≡ 1 (mod 10)
    1
    >>> 3 ^% (-1) :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
    7
    >>> 4 ^% (-1) :: Mod 10 -- 4 and 10 are not coprime
    (*** Exception: divide by zero