| Copyright | (c) 2017 Andrew Lelechenko |
|---|---|
| License | MIT |
| Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |
| Safe Haskell | Safe-Inferred |
| 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
Note: Mod 0 has no inhabitants, eventhough \( \mathbb{Z}/0\mathbb{Z} \) is technically isomorphic to \( \mathbb{Z} \).
Instances
| KnownNat m => Vector Vector (Mod m) | No validation checks are performed; reading untrusted data may corrupt internal invariants. |
Defined in Data.Mod Methods basicUnsafeFreeze :: Mutable Vector s (Mod m) -> ST s (Vector (Mod m)) # basicUnsafeThaw :: Vector (Mod m) -> ST s (Mutable Vector s (Mod m)) # basicLength :: Vector (Mod m) -> Int # basicUnsafeSlice :: Int -> Int -> Vector (Mod m) -> Vector (Mod m) # basicUnsafeIndexM :: Vector (Mod m) -> Int -> Box (Mod m) # basicUnsafeCopy :: Mutable Vector s (Mod m) -> Vector (Mod m) -> ST s () # | |
| KnownNat m => MVector MVector (Mod m) | No validation checks are performed; reading untrusted data may corrupt internal invariants. |
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 :: Int -> ST s (MVector s (Mod m)) # basicInitialize :: MVector s (Mod m) -> ST s () # basicUnsafeReplicate :: Int -> Mod m -> ST s (MVector s (Mod m)) # basicUnsafeRead :: MVector s (Mod m) -> Int -> ST s (Mod m) # basicUnsafeWrite :: MVector s (Mod m) -> Int -> Mod m -> ST s () # basicClear :: MVector s (Mod m) -> ST s () # basicSet :: MVector s (Mod m) -> Mod m -> ST s () # basicUnsafeCopy :: MVector s (Mod m) -> MVector s (Mod m) -> ST s () # basicUnsafeMove :: MVector s (Mod m) -> MVector s (Mod m) -> ST s () # basicUnsafeGrow :: MVector s (Mod m) -> Int -> ST s (MVector s (Mod m)) # | |
| KnownNat m => Storable (Mod m) | No validation checks are performed; reading untrusted data may corrupt internal invariants. |
| KnownNat m => Bounded (Mod m) | |
| KnownNat m => Enum (Mod m) | |
| Generic (Mod m) | |
| KnownNat m => Num (Mod m) | |
| KnownNat m => Read (Mod m) | Wrapping behaviour, similar to
the existing |
| KnownNat m => Fractional (Mod m) | Division by a residue, which is not
coprime
with the modulus, throws |
| KnownNat m => Real (Mod m) | |
Defined in Data.Mod Methods toRational :: Mod m -> Rational # | |
| Show (Mod m) | |
| NFData (Mod m) | |
| Eq (Mod m) | |
| Ord (Mod m) | |
| KnownNat m => Prim (Mod m) | No validation checks are performed; reading untrusted data may corrupt internal invariants. |
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 => Euclidean (Mod m) |
The instance is lawful only for
prime |
| KnownNat m => Field (Mod m) |
The instance is lawful only for
prime |
Defined in Data.Mod | |
| KnownNat m => GcdDomain (Mod m) |
The instance is lawful only for
prime |
| KnownNat m => Ring (Mod m) | |
| KnownNat m => Semiring (Mod m) | |
| KnownNat m => Unbox (Mod m) | No validation checks are performed; reading untrusted data may corrupt internal invariants. |
Defined in Data.Mod | |
| 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 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
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 => Monoid (MultMod m) Source # | |
| KnownNat m => Semigroup (MultMod m) Source # | |
| KnownNat m => Bounded (MultMod m) Source # | |
| Show (MultMod m) Source # | |
| Eq (MultMod m) Source # | |
| Ord (MultMod m) Source # | |
Defined in Math.NumberTheory.Moduli.Multiplicative | |
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
| Num SomeMod Source # | |
| Fractional SomeMod Source # | Beware that division by residue, which is not coprime with the modulo,
will result in runtime error. Consider using |
| Show SomeMod Source # | |
| Eq SomeMod Source # | |
| Ord SomeMod Source # | |
Defined in Math.NumberTheory.Moduli.SomeMod | |
| Euclidean SomeMod Source # | See the warning about division above. |
| Field SomeMod Source # | See the warning about division above. |
Defined in Math.NumberTheory.Moduli.SomeMod | |
| GcdDomain SomeMod Source # | See the warning about division above. |
| Ring SomeMod Source # | |
Defined in Math.NumberTheory.Moduli.SomeMod | |
| Semiring SomeMod Source # | |
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)