| Copyright | (c) 2017 Andrew Lelechenko |
|---|---|
| License | MIT |
| Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |
| Safe Haskell | None |
| Language | Haskell2010 |
Math.NumberTheory.Moduli.Class
Description
Safe modular arithmetic with modulo on type level.
Synopsis
- data Mod (m :: Nat)
- getVal :: Mod m -> Integer
- getNatVal :: Mod m -> Natural
- getMod :: KnownNat m => Mod m -> Integer
- getNatMod :: KnownNat m => Mod m -> Natural
- invertMod :: forall (m :: Nat). KnownNat m => Mod m -> Maybe (Mod m)
- powMod :: (KnownNat m, Integral a) => Mod m -> a -> Mod m
- (^%) :: forall (m :: Nat) a. (KnownNat m, Integral a) => Mod m -> a -> Mod m
- data MultMod m
- multElement :: MultMod m -> Mod m
- isMultElement :: KnownNat m => Mod m -> Maybe (MultMod m)
- invertGroup :: KnownNat m => MultMod m -> MultMod m
- data SomeMod where
- modulo :: Integer -> Natural -> SomeMod
- invertSomeMod :: SomeMod -> Maybe SomeMod
- powSomeMod :: Integral a => SomeMod -> a -> SomeMod
- class KnownNat (n :: Nat)
Known modulo
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
| KnownNat m => Vector Vector (Mod m) | |
Defined in Data.Mod 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 () # | |
| KnownNat m => MVector MVector (Mod m) | |
Defined in Data.Mod 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) | |
| KnownNat m => Enum (Mod m) | |
| Eq (Mod m) | |
| KnownNat m => Fractional (Mod m) | See the warning about division above. |
| KnownNat m => Num (Mod m) | |
| Ord (Mod m) | |
| KnownNat m => Show (Mod m) | |
| Generic (Mod m) | |
| KnownNat m => Storable (Mod m) | |
| KnownNat m => Unbox (Mod m) | |
Defined in Data.Mod | |
| NFData (Mod m) | |
| KnownNat m => Prim (Mod m) | |
Defined in Data.Mod Methods 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) | See the warning about division above. |
| KnownNat m => Euclidean (Mod m) | See the warning about division above. |
| KnownNat m => Field (Mod m) | See the warning about division above. |
Defined in Data.Mod | |
| KnownNat m => Semiring (Mod m) | |
| KnownNat m => Ring (Mod m) | |
| newtype MVector s (Mod m) | Unboxed vectors of |
| type Rep (Mod m) | |
| newtype Vector (Mod m) | Unboxed vectors of |
getVal :: Mod m -> Integer Source #
The canonical representative of the residue class, always between 0 and m-1 inclusively.
getNatVal :: Mod m -> Natural Source #
The canonical representative of the residue class, always between 0 and m-1 inclusively.
getMod :: KnownNat m => Mod m -> Integer Source #
Linking type and value levels: extract modulo m as a value.
getNatMod :: KnownNat m => Mod m -> Natural Source #
Linking type and value levels: extract modulo m as a value.
(^%) :: forall (m :: Nat) a. (KnownNat m, Integral a) => Mod m -> a -> Mod m infixr 8 #
Drop-in replacement for ^ with much 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
Multiplicative group
This type represents elements of the multiplicative group mod m, i.e.
those elements which are coprime to m. Use isMultElement to construct.
Instances
| KnownNat m => Bounded (MultMod m) Source # | |
| Eq (MultMod m) Source # | |
| Ord (MultMod m) Source # | |
Defined in Math.NumberTheory.Moduli.Multiplicative | |
| KnownNat m => Show (MultMod m) Source # | |
| KnownNat m => Semigroup (MultMod m) Source # | |
| KnownNat m => Monoid (MultMod m) Source # | |
multElement :: MultMod m -> Mod m Source #
Unwrap a residue.
isMultElement :: KnownNat m => Mod m -> Maybe (MultMod m) Source #
Attempt to construct a multiplicative group element.
invertGroup :: KnownNat m => MultMod m -> MultMod m Source #
For elements of the multiplicative group, we can safely perform the inverse without needing to worry about failure.
Unknown modulo
This type represents residues with unknown modulo and rational numbers. One can freely combine them in arithmetic expressions, but each operation will spend time on modulo's recalculation:
>>>2 `modulo` 10 + 4 `modulo` 15(1 `modulo` 5)>>>(2 `modulo` 10) * (4 `modulo` 15)(3 `modulo` 5)>>>import Data.Ratio>>>2 `modulo` 10 + fromRational (3 % 7)(1 `modulo` 10)>>>2 `modulo` 10 * fromRational (3 % 7)(8 `modulo` 10)
If performance is crucial, it is recommended to extract Mod m for further processing
by pattern matching. E. g.,
case modulo n m of
SomeMod k -> process k -- Here k has type Mod m
InfMod{} -> error "impossible"Instances
| Eq SomeMod Source # | |
| Fractional SomeMod Source # | Beware that division by residue, which is not coprime with the modulo,
will result in runtime error. Consider using |
| Num SomeMod Source # | |
| Ord SomeMod Source # | |
Defined in Math.NumberTheory.Moduli.SomeMod | |
| Show SomeMod Source # | |
| GcdDomain SomeMod Source # | See the warning about division above. |
| Euclidean SomeMod Source # | See the warning about division above. |
| Field SomeMod Source # | See the warning about division above. |
Defined in Math.NumberTheory.Moduli.SomeMod | |
| Semiring SomeMod Source # | |
| Ring SomeMod Source # | |
Defined in Math.NumberTheory.Moduli.SomeMod | |
modulo :: Integer -> Natural -> SomeMod infixl 7 Source #
Create modular value by representative of residue class and modulo.
One can use the result either directly (via functions from Num and Fractional),
or deconstruct it by pattern matching. Note that modulo never returns InfMod.
invertSomeMod :: SomeMod -> Maybe SomeMod Source #
Computes the inverse value, if it exists.
>>>invertSomeMod (3 `modulo` 10) -- because 3 * 7 = 1 :: Mod 10Just (7 `modulo` 10)>>>invertSomeMod (4 `modulo` 10)Nothing>>>import Data.Ratio>>>invertSomeMod (fromRational (2 % 5))Just 5 % 2
powSomeMod :: Integral a => SomeMod -> a -> SomeMod Source #
Drop-in replacement for ^, with much better performance.
When -O is enabled, there is a rewrite rule, which specialises ^ to powSomeMod.
>>>powSomeMod (3 `modulo` 10) 4(1 `modulo` 10)