mod 0.2.1.0 → 0.2.2.0

raw patch · 5 files changed

+124/−54 lines, 5 filesdep ~basePVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• Data/Mod.hs +19/−20
• Data/Mod/Word.hs +14/−11
• changelog.md +7/−0
• mod.cabal +3/−3
• test/Test.hs +81/−20

@@ -73,17 +73,18 @@ -- 1 -- -- __Note:__ 'Mod' 0 has no inhabitants, eventhough \( \mathbb{Z}/0\mathbb{Z} \) is technically isomorphic to \( \mathbb{Z} \).-newtype Mod (m :: Nat) = Mod-  { unMod :: Natural-  -- ^ The canonical representative of the residue class,-  -- always between 0 and \( m - 1 \) (inclusively).-  ---  -- >>> :set -XDataKinds-  -- >>> -1 :: Mod 10-  -- 9-  }+newtype Mod (m :: Nat) = Mod Natural   deriving (Eq, Ord, Generic) +-- | The canonical representative of the residue class,+-- always between 0 and \( m - 1 \) (inclusively).+--+-- >>> :set -XDataKinds+-- >>> -1 :: Mod 10+-- 9+unMod :: Mod m -> Natural+unMod (Mod w) = w+ instance NFData (Mod m)  instance Show (Mod m) where@@ -268,11 +269,11 @@   gcd (Mod x) (Mod y) = g     where       m = natVal g-      g = Mod $ if m > 1 then Prelude.gcd (Prelude.gcd m x) y else 0+      g = fromIntegral (Prelude.gcd (Prelude.gcd m x) y)   lcm (Mod x) (Mod y) = l     where       m = natVal l-      l = Mod $ if m > 1 then Prelude.lcm (Prelude.gcd m x) (Prelude.gcd m y) else 0+      l = fromIntegral (Prelude.lcm (Prelude.gcd m x) (Prelude.gcd m y))   coprime x y = Data.Euclidean.gcd x y == one  -- | 'Mod' @m@ is not even an@@ -370,19 +371,17 @@ -- 7 -- >>> 4 ^% (-1) :: Mod 10 -- 4 and 10 are not coprime -- (*** Exception: divide by zero-(^%) :: (KnownNat m, Integral a) => Mod m -> a -> Mod m+(^%) :: forall m a. (KnownNat m, Integral a) => Mod m -> a -> Mod m mx ^% a   | a < 0     = case invertMod mx of     Nothing ->  throw DivideByZero-    Just my ->  Mod $ powModNatural (unMod my) (fromIntegral' (-a)) (natVal mx)-  | otherwise = Mod $ powModNatural (unMod mx) (fromIntegral' a)    (natVal mx)+    Just my ->  Mod (powModNatural (unMod my) (absAsNatural a) (natVal mx))+  | otherwise = Mod $ powModNatural (unMod mx) (fromIntegral a) (natVal mx)   where-#if __GLASGOW_HASKELL__ == 900 && __GLASGOW_HASKELL_PATCHLEVEL1__ == 1-    -- Cannot use fromIntegral because of https://gitlab.haskell.org/ghc/ghc/-/issues/19411-    fromIntegral' = fromInteger . toInteger-#else-    fromIntegral' = fromIntegral-#endif+    -- Cannot simply 'negate' followed by 'fromIntegral', because for bounded+    -- types 'negate minBound = minBound' and thus still negative.+    absAsNatural :: a -> Natural+    absAsNatural = fromInteger . Prelude.negate . toInteger {-# INLINABLE [1] (^%) #-}  {-# SPECIALISE [1] (^%) :: KnownNat m => Mod m -> Integer -> Mod m #-}

@@ -68,15 +68,7 @@ -- 1 -- -- __Note:__ 'Mod' 0 has no inhabitants, eventhough \( \mathbb{Z}/0\mathbb{Z} \) is technically isomorphic to \( \mathbb{Z} \).-newtype Mod (m :: Nat) = Mod-  { unMod :: Word-  -- ^ The canonical representative of the residue class,-  -- always between 0 and \( m - 1 \) (inclusively).-  ---  -- >>> :set -XDataKinds-  -- >>> -1 :: Mod 10-  -- 9-  }+newtype Mod (m :: Nat) = Mod Word   deriving (Eq, Ord, Generic)   deriving Storable   -- ^ No validation checks are performed;@@ -87,6 +79,15 @@   -- reading untrusted data may corrupt internal invariants. #endif +-- | The canonical representative of the residue class,+-- always between 0 and \( m - 1 \) (inclusively).+--+-- >>> :set -XDataKinds+-- >>> -1 :: Mod 10+-- 9+unMod :: Mod m -> Word+unMod (Mod w) = w+ instance NFData (Mod m)  instance Show (Mod m) where@@ -257,11 +258,11 @@   gcd (Mod !x) (Mod !y) = g     where       m = getModulus (natVal g)-      g = Mod $ if m > 1 then P.gcd (P.gcd m x) y else 0+      g = fromIntegral (P.gcd (P.gcd m x) y)   lcm (Mod !x) (Mod !y) = l     where       m = getModulus (natVal l)-      l = Mod $ if m > 1 then P.lcm (P.gcd m x) (P.gcd m y) else 0+      l = fromIntegral (P.lcm (P.gcd m x) (P.gcd m y))   coprime x y = Data.Euclidean.gcd x y == one  -- | 'Mod' @m@ is not even an@@ -434,9 +435,11 @@ (^%) :: (KnownNat m, Integral a) => Mod m -> a -> Mod m mx@(Mod !x) ^% a = case natVal mx of   NatJ#{} -> tooLargeModulus+  1 -> Mod 0   m@(NatS# _)     | a < 0 -> case invertMod mx of       Nothing      -> throw DivideByZero+      -- Somewhat accidentally this works even if a = minBound       Just (Mod y) -> Mod $ f y (-a) 1     | otherwise    -> Mod $ f x a 1     where

@@ -1,3 +1,10 @@+# 0.2.2.0++* Plug a loophole to create `undefined {unMod = 100} :: Mod 1`.+* Fix `^%` when power is `minBound :: Int`.+* Fix `^%` when power is 0 and modulo is 1.+* Fix `Data.Euclidean.{gcd,lcm}` returning invalid inhabitants of `Mod m`.+ # 0.2.1.0  * Fix `invertMod (0 :: Mod 1)`.

@@ -1,5 +1,5 @@ name:          mod-version:       0.2.1.0+version:       0.2.2.0 cabal-version: >=1.10 build-type:    Simple license:       MIT@@ -15,7 +15,7 @@   Originally part of the <https://hackage.haskell.org/package/arithmoi arithmoi> package. category:      Math, Number Theory author:        Andrew Lelechenko <andrew.lelechenko@gmail.com>-tested-with:   GHC ==9.0.2 GHC ==9.2.8 GHC ==9.4.8 GHC ==9.6.7 GHC ==9.8.4 GHC ==9.10.2 GHC ==9.12.2 GHC ==9.14.1+tested-with:   GHC ==9.0.2 GHC ==9.2.8 GHC ==9.4.8 GHC ==9.6.7 GHC ==9.8.4 GHC ==9.10.3 GHC ==9.12.2 GHC ==9.14.1 extra-source-files:   changelog.md   README.md@@ -35,7 +35,7 @@  library   build-depends:-    base >=4.15 && <5,+    base >=4.15.1 && <5,     deepseq <1.6,     ghc-bignum <1.5   if flag(semirings)

@@ -10,6 +10,7 @@  import Control.Exception (evaluate, try, ArithException(..)) import Data.Bits+import Data.Maybe (isNothing) import Data.Mod import qualified Data.Mod.Word as Word import Data.Proxy@@ -78,11 +79,15 @@     , testProperty "invertMod"   invertModRandomProp     , testProperty "powMod"      powModRandomProp     , testProperty "powMod on sum" powModRandomAdditiveProp-    , testProperty "powMod special case" powModCase+    , testProperty "powMod special case 1" powModCase1+    , testProperty "powMod special case 2" powModCase2+    , testProperty "powMod on minBound" powModMinBoundProp #ifdef MIN_VERSION_semirings     , testProperty "divide"  dividePropRandom-    , testProperty "gcd"     gcdIsPrincipalIdealRandom-    , testProperty "lcm"     lcmIsIntersectionOfIdealsRandom+    , testProperty "gcd is valid" gcdIsValid+    , testProperty "gcd is principal ideal" gcdIsPrincipalIdealRandom+    , testProperty "lcm is valid" lcmIsValid+    , testProperty "lcm is intersection of ideals" lcmIsIntersectionOfIdealsRandom     , testProperty "coprime" coprimeGeneratorsRandom     , testProperty "quotRem" quotRemPropRandom     , testProperty "degree"  degreePropRandom@@ -126,11 +131,15 @@     , testProperty "invertMod near maxBound" invertModWordRandomPropNearMaxBound     , testProperty "powMod"      powModWordRandomProp     , testProperty "powMod on sum" powModWordRandomAdditiveProp-    , testProperty "powMod special case" powModWordCase+    , testProperty "powMod special case 1" powModWordCase1+    , testProperty "powMod special case 2" powModWordCase2+    , testProperty "powMod on minBound" powModWordMinBoundProp #ifdef MIN_VERSION_semirings     , testProperty "divide"  divideWordPropRandom-    , testProperty "gcd"     gcdIsPrincipalIdealWordRandom-    , testProperty "lcm"     lcmIsIntersectionOfIdealsWordRandom+    , testProperty "gcd is valid" gcdIsValidWord+    , testProperty "gcd is principal ideal" gcdIsPrincipalIdealWordRandom+    , testProperty "lcm is valid" lcmIsValidWord+    , testProperty "lcm is intersection of ideals" lcmIsIntersectionOfIdealsWordRandom     , testProperty "coprime" coprimeGeneratorsWordRandom     , testProperty "quotRem" quotRemWordPropRandom     , testProperty "degree"  degreeWordPropRandom@@ -211,7 +220,7 @@ -- fromInteger  fromIntegerRandomProp :: Positive Integer -> Integer -> Property-fromIntegerRandomProp (Positive m) n = m > 1 ==> case someNatVal (fromInteger m) of+fromIntegerRandomProp (Positive m) n = m >= 1 ==> case someNatVal (fromInteger m) of   SomeNat p -> fromIntegerProp p n  fromIntegerProp :: forall m. KnownNat m => Proxy m -> Integer -> Property@@ -221,7 +230,7 @@     m = fromInteger n  fromIntegerWordRandomProp :: Word -> Integer -> Property-fromIntegerWordRandomProp m n = m > 1 ==> case someNatVal (fromIntegral m) of+fromIntegerWordRandomProp m n = m >= 1 ==> case someNatVal (fromIntegral m) of   SomeNat p -> fromIntegerWordProp p n  fromIntegerWordProp :: forall m. KnownNat m => Proxy m -> Integer -> Property@@ -234,7 +243,7 @@ -- invertMod  invertModRandomProp :: Positive Integer -> Integer -> Property-invertModRandomProp (Positive m) n = m > 1 ==> case someNatVal (fromInteger m) of+invertModRandomProp (Positive m) n = m >= 1 ==> case someNatVal (fromInteger m) of   SomeNat (Proxy :: Proxy m) -> invertModProp (fromInteger n :: Mod m)  invertModProp :: KnownNat m => Mod m -> Property@@ -245,7 +254,7 @@     g = gcd (unMod x) (fromIntegral (natVal x))  invertModWordRandomProp :: Word -> Integer -> Property-invertModWordRandomProp m n = m > 1 ==> case someNatVal (fromIntegral m) of+invertModWordRandomProp m n = m >= 1 ==> case someNatVal (fromIntegral m) of   SomeNat (Proxy :: Proxy m) -> invertModWordProp (fromInteger n :: Word.Mod m)  invertModWordRandomPropNearMaxBound :: Word -> Integer -> Property@@ -264,7 +273,7 @@ -- powMod  powModRandomProp :: Positive Integer -> Integer -> Int -> Property-powModRandomProp (Positive m) x n = m > 1 ==> case someNatVal (fromInteger m) of+powModRandomProp (Positive m) x n = m >= 1 ==> case someNatVal (fromInteger m) of   SomeNat (Proxy :: Proxy m) -> powModProp (fromInteger x :: Mod m) n  powModProp :: KnownNat m => Mod m -> Int -> Property@@ -275,23 +284,33 @@     Just x' -> x ^% n === getProduct (stimes (-n) (Product x'))  powModRandomAdditiveProp :: Positive Integer -> Integer -> Huge Integer -> Huge Integer -> Property-powModRandomAdditiveProp (Positive m) x (Huge n1) (Huge n2) = m > 1 ==> case someNatVal (fromInteger m) of+powModRandomAdditiveProp (Positive m) x (Huge n1) (Huge n2) = m >= 1 ==> case someNatVal (fromInteger m) of   SomeNat (Proxy :: Proxy m) -> powModAdditiveProp (fromInteger x :: Mod m) n1 n2  powModAdditiveProp :: KnownNat m => Mod m -> Integer -> Integer -> Property powModAdditiveProp x n1 n2-  | invertMod x == Nothing, n1 < 0 || n2 < 0+  | isNothing (invertMod x), n1 < 0 || n2 < 0   = property True   | otherwise   = (x ^% n1) * (x ^% n2) === x ^% (n1 + n2) -powModCase :: Property-powModCase = once $ 0 ^% n === (0 :: Mod 2)+powModCase1 :: Property+powModCase1 = once $ 0 ^% n === (0 :: Mod 2)   where     n = 1 `shiftL` 64 :: Integer +powModCase2 :: Property+powModCase2 = once $ 1 ^% 0 === (0 :: Mod 1)++powModMinBoundProp :: Positive Integer -> Integer -> Property+powModMinBoundProp (Positive m) x = case someNatVal (fromIntegral m) of+  SomeNat (Proxy :: Proxy m) -> let x' = fromInteger x :: Mod m in+    case invertMod x' of+      Nothing -> property True+      Just{} -> x' ^% (minBound :: Int) === x' ^% toInteger (minBound :: Int)+ powModWordRandomProp :: Word -> Integer -> Int -> Property-powModWordRandomProp m x k = m > 1 ==> case someNatVal (fromIntegral m) of+powModWordRandomProp m x k = m >= 1 ==> case someNatVal (fromIntegral m) of   SomeNat (Proxy :: Proxy m) -> powModWordProp (fromInteger x :: Word.Mod m) k  powModWordProp :: KnownNat m => Word.Mod m -> Int -> Property@@ -302,21 +321,31 @@     Just x' -> x Word.^% n === getProduct (stimes (-n) (Product x'))  powModWordRandomAdditiveProp :: Word -> Integer -> Huge Integer -> Huge Integer -> Property-powModWordRandomAdditiveProp m x (Huge n1) (Huge n2) = m > 1 ==> case someNatVal (fromIntegral m) of+powModWordRandomAdditiveProp m x (Huge n1) (Huge n2) = m >= 1 ==> case someNatVal (fromIntegral m) of   SomeNat (Proxy :: Proxy m) -> powModWordAdditiveProp (fromInteger x :: Word.Mod m) n1 n2  powModWordAdditiveProp :: KnownNat m => Word.Mod m -> Integer -> Integer -> Property powModWordAdditiveProp x n1 n2-  | Word.invertMod x == Nothing, n1 < 0 || n2 < 0+  | isNothing (Word.invertMod x), n1 < 0 || n2 < 0   = property True   | otherwise   = (x Word.^% n1) * (x Word.^% n2) === x Word.^% (n1 + n2) -powModWordCase :: Property-powModWordCase = once $ 0 Word.^% n === (0 :: Word.Mod 2)+powModWordCase1 :: Property+powModWordCase1 = once $ 0 Word.^% n === (0 :: Word.Mod 2)   where     n = 1 `shiftL` 64 :: Integer +powModWordCase2 :: Property+powModWordCase2 = once $ 1 Word.^% 0 === (0 :: Word.Mod 1)++powModWordMinBoundProp :: Word -> Integer -> Property+powModWordMinBoundProp m x = m >= 1 ==> case someNatVal (fromIntegral m) of+  SomeNat (Proxy :: Proxy m) -> let x' = fromInteger x :: Word.Mod m in+    case Word.invertMod x' of+      Nothing -> property True+      Just{} -> x' Word.^% (minBound :: Int) === x' Word.^% toInteger (minBound :: Int)+ newtype Huge a = Huge { _getHuge :: a }   deriving (Show) @@ -350,6 +379,14 @@   Just z -> x === y * z   Nothing -> filter ((== x) . (* y)) [minBound .. maxBound] === [] +gcdIsValid :: Positive Integer -> Integer -> Integer -> Property+gcdIsValid (Positive m) x y = case someNatVal (fromInteger m) of+  SomeNat (Proxy :: Proxy m) -> fromIntegral (unMod g) === g+    where+      x' = fromInteger x :: Mod m+      y' = fromInteger y :: Mod m+      g = E.gcd x' y'+ gcdIsPrincipalIdealRandom :: Positive (Small Integer) -> Integer -> Integer -> Property gcdIsPrincipalIdealRandom (Positive (Small m)) x y = case someNatVal (fromInteger m) of   SomeNat (Proxy :: Proxy m) -> gcdIsPrincipalIdeal (fromInteger x :: Mod m) (fromInteger y)@@ -360,6 +397,14 @@     genIdeal t = S.fromList $ map (* t) [minBound .. maxBound]     addIdeals us vs = S.fromList [ u + v | u <- S.toList us, v <- S.toList vs ] +lcmIsValid :: Positive Integer -> Integer -> Integer -> Property+lcmIsValid (Positive m) x y = case someNatVal (fromInteger m) of+  SomeNat (Proxy :: Proxy m) -> fromIntegral (unMod l) === l+    where+      x' = fromInteger x :: Mod m+      y' = fromInteger y :: Mod m+      l = E.lcm x' y'+ lcmIsIntersectionOfIdealsRandom :: Positive (Small Integer) -> Integer -> Integer -> Property lcmIsIntersectionOfIdealsRandom (Positive (Small m)) x y = case someNatVal (fromInteger m) of   SomeNat (Proxy :: Proxy m) -> lcmIsIntersectionOfIdeals (fromInteger x :: Mod m) (fromInteger y)@@ -410,6 +455,14 @@   Just z -> x === y * z   Nothing -> filter ((== x) . (* y)) [minBound .. maxBound] === [] +gcdIsValidWord :: Positive Word -> Integer -> Integer -> Property+gcdIsValidWord (Positive m) x y = case someNatVal (fromIntegral m) of+  SomeNat (Proxy :: Proxy m) -> fromIntegral (Word.unMod g) === g+    where+      x' = fromInteger x :: Word.Mod m+      y' = fromInteger y :: Word.Mod m+      g = E.gcd x' y'+ gcdIsPrincipalIdealWordRandom :: Positive Word -> Word -> Word -> Property gcdIsPrincipalIdealWordRandom (Positive m) x y = case someNatVal (fromIntegral m) of   SomeNat (Proxy :: Proxy m) -> gcdIsPrincipalIdealWord (fromIntegral x :: Word.Mod m) (fromIntegral y)@@ -419,6 +472,14 @@   where     genIdeal t = S.fromList $ map (* t) [minBound .. maxBound]     addIdeals us vs = S.fromList [ u + v | u <- S.toList us, v <- S.toList vs ]++lcmIsValidWord :: Positive Word -> Integer -> Integer -> Property+lcmIsValidWord (Positive m) x y = case someNatVal (fromIntegral m) of+  SomeNat (Proxy :: Proxy m) -> fromIntegral (Word.unMod l) === l+    where+      x' = fromInteger x :: Word.Mod m+      y' = fromInteger y :: Word.Mod m+      l = E.lcm x' y'  lcmIsIntersectionOfIdealsWordRandom :: Positive Word -> Word -> Word -> Property lcmIsIntersectionOfIdealsWordRandom (Positive m) x y = case someNatVal (fromIntegral m) of