arithmoi 0.13.0.0 → 0.13.0.1

raw patch · 23 files changed

+88/−74 lines, 23 filesdep ~QuickCheckdep ~containersdep ~ghc-bignumPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: QuickCheck, containers, ghc-bignum, tasty, tasty-bench, tasty-quickcheck

API changes (from Hackage documentation)

Files

• Math/NumberTheory/ArithmeticFunctions/Class.hs +0/−1
• Math/NumberTheory/ArithmeticFunctions/Inverse.hs +1/−1
• Math/NumberTheory/ArithmeticFunctions/Moebius.hs +0/−1
• Math/NumberTheory/ArithmeticFunctions/SieveBlock.hs +1/−1
• Math/NumberTheory/ArithmeticFunctions/Standard.hs +0/−7
• Math/NumberTheory/DirichletCharacters.hs +0/−1
• Math/NumberTheory/Euclidean/Coprimes.hs +0/−1
• Math/NumberTheory/Moduli/Equations.hs +1/−1
• Math/NumberTheory/Moduli/Multiplicative.hs +0/−1
• Math/NumberTheory/Primes/Factorisation/Montgomery.hs +2/−2
• Math/NumberTheory/Primes/IntSet.hs +15/−2
• Math/NumberTheory/Primes/Testing/Certified.hs +2/−1
• Math/NumberTheory/RootsOfUnity.hs +0/−1
• arithmoi.cabal +13/−13
• benchmark/Math/NumberTheory/PrimesBench.hs +3/−1
• changelog.md +6/−0
• test-suite/Math/NumberTheory/ArithmeticFunctionsTests.hs +9/−8
• test-suite/Math/NumberTheory/EisensteinIntegersTests.hs +1/−1
• test-suite/Math/NumberTheory/GaussianIntegersTests.hs +2/−2
• test-suite/Math/NumberTheory/Moduli/SqrtTests.hs +7/−6
• test-suite/Math/NumberTheory/Recurrences/BilinearTests.hs +12/−9
• test-suite/Math/NumberTheory/Recurrences/PentagonalTests.hs +11/−13
• test-suite/Math/NumberTheory/TestUtils/MyCompose.hs +2/−0

@@ -62,7 +62,6 @@  instance Monoid a => Monoid (ArithmeticFunction n a) where   mempty  = pure mempty-  mappend = (<>)  -- | Factorisation is expensive, so it is better to avoid doing it twice. -- Write 'runFunction (f + g) n' instead of 'runFunction f n + runFunction g n'.

@@ -27,7 +27,7 @@     asSetOfPreimages   ) where -import Prelude hiding (rem, quot)+import Prelude hiding (rem, quot, Foldable(..)) import Data.Bits (Bits) import Data.Euclidean import Data.Foldable

@@ -113,7 +113,6 @@  instance Monoid Moebius where   mempty  = MoebiusP-  mappend = (<>)  -- | Evaluate the Möbius function over a block. -- Value of @f@ at 0, if zero falls into block, is undefined.

@@ -97,7 +97,7 @@   -> V.Vector a runFunctionOverBlock (ArithmeticFunction f g) = (G.map g .) . sieveBlock SieveBlockConfig   { sbcEmpty                = mempty-  , sbcAppend               = mappend+  , sbcAppend               = (<>)   , sbcFunctionOnPrimePower = coerce f   } 

@@ -296,7 +296,6 @@  instance Monoid (Mangoldt a) where   mempty  = MangoldtZero-  mappend = (<>)  -- | See 'isNFreeA'. isNFree :: UniqueFactorisation n => Word -> n -> Bool@@ -315,7 +314,6 @@  instance Integral a => Monoid (LCM a) where   mempty  = LCM 1-  mappend = (<>)  newtype Xor = Xor { _getXor :: Bool } @@ -329,7 +327,6 @@  instance Monoid Xor where   mempty  = Xor False-  mappend = (<>)  newtype SetProduct a = SetProduct { getSetProduct :: Set a } @@ -338,7 +335,6 @@  instance (Num a, Ord a) => Monoid (SetProduct a) where   mempty  = SetProduct mempty-  mappend = (<>)  newtype ListProduct a = ListProduct { getListProduct :: [a] } @@ -347,7 +343,6 @@  instance Num a => Monoid (ListProduct a) where   mempty  = ListProduct mempty-  mappend = (<>)  -- Represent as a Reader monad newtype BoundedSetProduct a = BoundedSetProduct { _getBoundedSetProduct :: a -> Set a }@@ -364,7 +359,6 @@  instance (Ord a, Num a) => Monoid (BoundedSetProduct a) where   mempty = BoundedSetProduct mempty-  mappend = (<>)  newtype IntSetProduct = IntSetProduct { getIntSetProduct :: IntSet } @@ -373,4 +367,3 @@  instance Monoid IntSetProduct where   mempty  = IntSetProduct mempty-  mappend = (<>)

@@ -204,7 +204,6 @@  instance KnownNat n => Monoid (DirichletCharacter n) where   mempty = principalChar-  mappend = (<>)  stimesChar :: Integral a => a -> DirichletCharacter n -> DirichletCharacter n stimesChar s (Generated xs) = Generated (map mult xs)

@@ -121,7 +121,6 @@  instance (Eq a, GcdDomain a, Eq b, Num b) => Monoid (Coprimes a b) where   mempty  = Coprimes []-  mappend = (<>)  -- | The input list is assumed to be a factorisation of some number -- into a list of powers of (possibly, composite) non-zero factors. The output

@@ -123,7 +123,7 @@   -> Integer   -> Prime Integer   -> [Integer]-solveQuadraticPrime a b c (unPrime -> 2 :: Integer)+solveQuadraticPrime a b c (unPrime -> (2 :: Integer))   = case (even c, even (a + b)) of     (True, True) -> [0, 1]     (True, _)    -> [0]

@@ -49,7 +49,6 @@  instance KnownNat m => Monoid (MultMod m) where   mempty = MultMod 1-  mappend = (<>)  instance KnownNat m => Bounded (MultMod m) where   minBound = MultMod 1

@@ -33,13 +33,14 @@   , findParms   ) where +import Prelude hiding (Foldable(..)) import Control.Arrow import Control.Monad.Trans.State.Lazy import Data.Array.Base (bounds, unsafeAt) import Data.Bits+import Data.Foldable import Data.IntMap (IntMap) import qualified Data.IntMap as IM-import Data.List (foldl') import Data.Maybe import Data.Mod import Data.Proxy@@ -197,7 +198,6 @@  instance Monoid Factors where   mempty = Factors [] []-  mappend = (<>)  modifyPowers :: (Word -> Word) -> Factors -> Factors modifyPowers f (Factors pfs cfs)

@@ -13,6 +13,7 @@ --  {-# LANGUAGE BangPatterns               #-}+{-# LANGUAGE CPP                        #-} {-# LANGUAGE DeriveDataTypeable         #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-} {-# LANGUAGE ScopedTypeVariables        #-}@@ -74,20 +75,24 @@   , toDescList   ) where -import Prelude ((>), (/=), (==), (-), Eq, Ord, Show, Monoid, Bool, Maybe(..), Int, Word, otherwise)+import Prelude (Eq, Ord, Show, Monoid, Bool, Maybe(..), Int, otherwise) import Control.DeepSeq (NFData) import Data.Coerce (coerce) import Data.Data (Data)-import Data.Function (on) import Data.IntSet (IntSet) import qualified Data.IntSet.Internal as IS import Data.Semigroup (Semigroup) import qualified GHC.Exts (IsList(..))  import Math.NumberTheory.Primes.Types (Prime(..))++#if !MIN_VERSION_containers(0,8,0)+import Prelude ((>), (/=), (==), (-), Word)+import Data.Function (on) import Math.NumberTheory.Utils.FromIntegral (wordToInt, intToWord) import Data.Bits (Bits(..)) import Utils.Containers.Internal.BitUtil (highestBitMask)+#endif  -- | A set of 'Prime' integers. newtype PrimeIntSet = PrimeIntSet {@@ -194,7 +199,11 @@  -- | Symmetric difference of two sets of primes. symmetricDifference :: PrimeIntSet -> PrimeIntSet -> PrimeIntSet+#if MIN_VERSION_containers(0,8,0)+symmetricDifference = coerce IS.symmetricDifference+#else symmetricDifference = coerce symmDiff+#endif  -- | Intersection of a set of primes and a set of integers. intersection :: PrimeIntSet -> IntSet -> PrimeIntSet@@ -270,6 +279,8 @@ ------------------------------------------------------------------------------- -- IntSet helpers +#if !MIN_VERSION_containers(0,8,0)+ -- | Symmetric difference of two sets. -- Implementation is inspired by 'Data.IntSet.union' -- and 'Data.IntSet.difference'.@@ -329,3 +340,5 @@ mask :: Int -> Int -> Int mask i m = i .&. (complement (m - 1) `xor` m) {-# INLINE mask #-}++#endif

@@ -16,8 +16,9 @@   ( isCertifiedPrime   ) where -import Data.List (foldl')+import Prelude hiding (Foldable(..)) import Data.Bits ((.&.))+import Data.Foldable import Data.Mod import Data.Proxy import GHC.Num.Integer

@@ -53,7 +53,6 @@   stimes k (RootOfUnity q) = toRootOfUnity (q * (toInteger k % 1))  instance Monoid RootOfUnity where-  mappend = (<>)   mempty = RootOfUnity 0  -- | Convert a root of unity into an inexact complex number. Due to floating point inaccuracies,

@@ -1,5 +1,5 @@ name:          arithmoi-version:       0.13.0.0+version:       0.13.0.1 cabal-version: 2.0 build-type:    Simple license:       MIT@@ -17,7 +17,7 @@   powers (integer roots and tests, modular exponentiation). category:      Math, Algorithms, Number Theory author:        Andrew Lelechenko, Daniel Fischer-tested-with:   GHC ==9.0.2 GHC ==9.2.8 GHC ==9.4.5 GHC ==9.6.2+tested-with:   GHC ==9.0.2 GHC ==9.2.8 GHC ==9.4.8 GHC ==9.6.6 GHC ==9.8.4 GHC ==9.10.1 GHC ==9.12.1 extra-doc-files:   changelog.md @@ -29,19 +29,19 @@   build-depends:     base >=4.15 && <5,     array >=0.5 && <0.6,-    containers >=0.5.11 && <0.7,-    chimera >=0.3 && <0.4,-    constraints <0.14,+    containers >=0.5.11 && <0.9,+    chimera >=0.3 && <0.5,+    constraints <0.15,     deepseq <1.6,     exact-pi >=0.5 && <0.6,-    ghc-bignum <1.4,+    ghc-bignum <1.5,     infinite-list <0.2,     integer-logarithms >=1.0 && <1.1,     integer-roots >=1.0 && <1.1,     mod <0.3,-    random >=1.0 && <1.3,+    random >=1.0 && <1.4,     transformers >=0.4 && <0.7,-    semirings >=0.5.2 && <0.7,+    semirings >=0.5.2 && <0.8,     vector >=0.12 && <0.14   exposed-modules:     Math.NumberTheory.ArithmeticFunctions@@ -113,14 +113,14 @@     infinite-list,     integer-roots >=1.0,     mod,-    QuickCheck >=2.10 && <2.15,+    QuickCheck >=2.10 && <2.16,     quickcheck-classes >=0.6.3 && <0.7,-    random >=1.0 && <1.3,+    random,     semirings >=0.2,     smallcheck >=1.2 && <1.3,-    tasty >=0.10 && <1.5,+    tasty >=0.10 && <1.6,     tasty-hunit >=0.9 && <0.11,-    tasty-quickcheck >=0.9 && <0.11,+    tasty-quickcheck >=0.9 && <0.12,     tasty-rerun >=1.1.17 && <1.2,     tasty-smallcheck >=0.8 && <0.9,     transformers >=0.5,@@ -185,7 +185,7 @@     mod,     random,     semirings,-    tasty-bench < 0.4,+    tasty-bench >= 0.4 && < 0.5,     vector   other-modules:     Math.NumberTheory.ArithmeticFunctionsBench

@@ -1,4 +1,6 @@-{-# OPTIONS_GHC -fno-warn-type-defaults #-}+{-# OPTIONS_GHC -Wno-type-defaults #-}+{-# OPTIONS_GHC -Wno-x-partial #-}+{-# OPTIONS_GHC -Wno-unrecognised-warning-flags #-}  module Math.NumberTheory.PrimesBench   ( benchSuite

@@ -1,5 +1,11 @@ # Changelog +## 0.13.0.1++### Fixed++* Compatibility patches for `containers-0.8`.+ ## 0.13.0.0  ### Changed

@@ -288,14 +288,15 @@     in take m (filter (isNFree n') [1 ..]) == take m (nFrees n' :: [Integer])  nFreedomProperty3 :: Power Word -> Positive Int -> Bool-nFreedomProperty3 (Power n) (Positive m) =-    let n' | n == maxBound = n-           | otherwise     = n + 1-        zet = 1 / zetas 1e-14 Inf.!! n' :: Double-        m' = 100 * m-        nfree = fromIntegral m' /-                fromIntegral (head (drop (m' - 1) $ nFrees n' :: [Integer]))-    in 1 / fromIntegral m >= abs (zet - nfree)+nFreedomProperty3 (Power n) (Positive m) = case drop (m' - 1) $ nFrees n :: [Integer] of+  [] -> True+  x : _ -> 1 / fromIntegral m >= abs (zet - fromIntegral m' / fromIntegral x)+  where+    zet :: Double+    zet = 1 / zetas 1e-14 Inf.!! n++    m' :: Int+    m' = 100 * m  -- | -- * Using a bounded integer type like @Int@ instead of @Integer@ here means

@@ -107,7 +107,7 @@ primesProperty2 :: Positive Int -> Bool primesProperty2 (Positive index) =     let isOrdered :: [Prime E.EisensteinInteger] -> Bool-        isOrdered xs = all (\(x, y) -> E.norm (unPrime x) <= E.norm (unPrime y)) . zip xs $ tail xs+        isOrdered xs = all (\(x, y) -> E.norm (unPrime x) <= E.norm (unPrime y)) . zip xs $ drop 1 xs     in isOrdered $ Inf.take index E.primes  -- | Checks that the numbers produced by @primes@ are all in the first

@@ -73,7 +73,7 @@         k  = integerSquareRoot (unPrime p)         bs = [1 .. k]         asbs = map (\b' -> ((b' * c) `mod` unPrime p, b')) bs-        (a, b) = head [ (a', b') | (a', b') <- asbs, a' <= k]+        (a, b) : _ = [ (a', b') | (a', b') <- asbs, a' <= k]     in a :+ b  findPrimeProperty1 :: Prime Integer -> Bool@@ -113,7 +113,7 @@  -- | Check that primes generates the primes in order. orderingPrimes :: Assertion-orderingPrimes = assertBool "primes are ordered" (and $ zipWith (<=) xs (tail xs))+orderingPrimes = assertBool "primes are ordered" (and $ zipWith (<=) xs (drop 1 xs))   where xs = map (norm . unPrime) $ Inf.take 1000 primes  numberOfPrimes :: Assertion

@@ -20,8 +20,9 @@ import Test.Tasty.HUnit  import Control.Arrow-import Data.List (group, sort)-import Data.Maybe (fromJust)+import Data.List (sort)+import qualified Data.List.NonEmpty as NE+import Data.Maybe (fromJust, listToMaybe) import Numeric.Natural  import Math.NumberTheory.Moduli hiding (invertMod)@@ -32,7 +33,7 @@ unwrapPP (p, Power e) = (p, e `mod` 5)  nubOrd :: Ord a => [a] -> [a]-nubOrd = map head . group . sort+nubOrd = map NE.head . NE.group . sort  -- | Check that 'sqrtMod' is defined iff a quadratic residue exists. --   Also check that the result is a solution of input modular equation.@@ -60,7 +61,7 @@ tonelliShanksProperty2 :: Prime Integer -> Bool tonelliShanksProperty2 p'@(unPrime -> p) = p `mod` 4 /= 1 || (rt ^ 2 - n) `rem` p == 0   where-    n  = head $ filter (\s -> jacobi s p == One) [2..p-1]+    n : _ = filter (\s -> jacobi s p == One) [2..p-1]     rt : _ = sqrtsModPrime n p'  tonelliShanksProperty3 :: Prime Integer -> Bool@@ -72,11 +73,11 @@  tonelliShanksSpecialCases :: Assertion tonelliShanksSpecialCases =-  assertEqual "OEIS A002224" [6, 32, 219, 439, 1526, 2987, 22193, 11740, 13854, 91168, 326277, 232059, 3230839, 4379725, 11754394, 32020334, 151024619, 345641931, 373671108, 1857111865, 8110112775, 4184367042] rts+  assertEqual "OEIS A002224" (map Just [6, 32, 219, 439, 1526, 2987, 22193, 11740, 13854, 91168, 326277, 232059, 3230839, 4379725, 11754394, 32020334, 151024619, 345641931, 373671108, 1857111865, 8110112775, 4184367042]) rts   where     ps :: [Integer]     ps = [17, 73, 241, 1009, 2689, 8089, 33049, 53881, 87481, 483289, 515761, 1083289, 3818929, 9257329, 22000801, 48473881, 175244281, 427733329, 898716289, 8114538721, 9176747449, 23616331489]-    rts = map (head . sqrtsModPrime 2 . fromJust . isPrime) ps+    rts = map (listToMaybe . sqrtsModPrime 2 . fromJust . isPrime) ps  sqrtsModPrimePowerProperty1 :: AnySign Integer -> (Prime Integer, Power Word) -> Bool sqrtsModPrimePowerProperty1 (AnySign n) (p'@(unPrime -> p), Power e) = gcd n p > 1

@@ -31,7 +31,7 @@ binomialProperty1 i = length (binomial @Integer Inf.!! i) == fromIntegral i + 1  binomialProperty2 :: Word -> Bool-binomialProperty2 i = head (binomial @Integer Inf.!! i) == 1+binomialProperty2 i = take 1 (binomial @Integer Inf.!! i) == [1]  binomialProperty3 :: Word -> Bool binomialProperty3 i = binomial @Integer Inf.!! i !! fromIntegral i == 1@@ -91,8 +91,8 @@  stirling1Property2 :: Word -> Bool stirling1Property2 i-  =  head (stirling1 Inf.!! i)-  == if i == 0 then 1 else 0+  =  take 1 (stirling1 Inf.!! i)+  == [if i == 0 then 1 else 0]  stirling1Property3 :: Word -> Bool stirling1Property3 i = stirling1 Inf.!! i !! fromIntegral i == 1@@ -109,8 +109,8 @@  stirling2Property2 :: Word -> Bool stirling2Property2 i-  =  head (stirling2 Inf.!! i)-  == if i == 0 then 1 else 0+  =  take 1 (stirling2 Inf.!! i)+  == [if i == 0 then 1 else 0]  stirling2Property3 :: Word -> Bool stirling2Property3 i = stirling2 Inf.!! i !! fromIntegral i == 1@@ -127,8 +127,8 @@  lahProperty2 :: Word -> Bool lahProperty2 i-  =  head (lah Inf.!! i)-  == product [1 .. i+1]+  =  take 1 (lah Inf.!! i)+  == [product [1 .. i+1]]  lahProperty3 :: Word -> Bool lahProperty3 i = lah Inf.!! i !! fromIntegral i == 1@@ -143,7 +143,9 @@ eulerian1Property1 i = length (eulerian1 Inf.!! i) == fromIntegral i  eulerian1Property2 :: Positive Int -> Bool-eulerian1Property2 (Positive i) = head (eulerian1 Inf.!! fromIntegral i) == 1+eulerian1Property2 (Positive i)+  =  take 1 (eulerian1 Inf.!! fromIntegral i)+  == [1]  eulerian1Property3 :: Positive Int -> Bool eulerian1Property3 (Positive i) = eulerian1 Inf.!! fromIntegral i !! (i - 1) == 1@@ -160,7 +162,8 @@  eulerian2Property2 :: Positive Int -> Bool eulerian2Property2 (Positive i)-  = head (eulerian2 Inf.!! fromIntegral i) == 1+  =  take 1 (eulerian2 Inf.!! fromIntegral i)+  == [1]  eulerian2Property3 :: Positive Int -> Bool eulerian2Property3 (Positive i)

@@ -7,6 +7,7 @@ -- Tests for Math.NumberTheory.Recurrences.Pentagonal -- +{-# LANGUAGE PostfixOperators    #-} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE ViewPatterns        #-} @@ -16,7 +17,7 @@   ( testSuite   ) where -import Data.List.Infinite (Infinite(..))+import Data.List.Infinite (Infinite(..), (...)) import qualified Data.List.Infinite as Inf import Data.Proxy                    (Proxy (..)) import GHC.Natural                   (Natural)@@ -39,9 +40,9 @@ -- while @2@ is the @2 * 2 - 1 == 3@-rd, and so on. pentagonalNumbersProperty1 :: AnySign Int -> Bool pentagonalNumbersProperty1 (AnySign n)-    | n == 0    = head pents           == 0-    | n > 0     = pents !! (2 * n - 1) == pent n-    | otherwise = pents !! (2 * abs n) == pent n+    | n == 0    = Inf.head pents           == 0+    | n > 0     = pents Inf.!! (2 * fromIntegral n - 1) == pent n+    | otherwise = pents Inf.!! (2 * fromIntegral (- n)) == pent n   where     pent m = div (3 * (m * m) - m) 2 @@ -59,13 +60,10 @@  -- | Copied from @Math.NumberTheory.Recurrences.Pentagonal@ to test the -- reference implementation of @partition@.-pents :: (Enum a, Num a) => [a]-pents = interleave (scanl (\acc n -> acc + 3 * n - 1) 0 [1..])-                   (scanl (\acc n -> acc + 3 * n - 2) 1 [2..])-  where-    interleave :: [a] -> [a] -> [a]-    interleave (n : ns) (m : ms) = n : m : interleave ns ms-    interleave _ _ = []+pents :: (Enum a, Num a) => Infinite a+pents = Inf.interleave+  (Inf.scanl (\acc n -> acc + 3 * n - 1) 0 (1...))+  (Inf.scanl (\acc n -> acc + 3 * n - 2) 1 (2...))  -- | Check that @p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-11) + ...@, -- where @p(x) = 0@ for any negative integer and @p(0) = 1@.@@ -74,8 +72,8 @@     partition' n == (sum .                      pentagonalSigns .                      map (\m -> partition' (n - m)) .-                     takeWhile (\m -> n - m >= 0) .-                     tail $ pents)+                     Inf.takeWhile (\m -> n - m >= 0) .+                     Inf.tail $ pents)  -- | Check that -- @partition :: [Math.NumberTheory.Moduli.Mod n] == map (`mod` n) partition@.

@@ -23,6 +23,8 @@ import Test.QuickCheck (Arbitrary) import Test.SmallCheck.Series (Serial) +-- | As of @base-4.19@ Data.Functor.Compose has every instance we need,+-- except for instance Arbitrary, which overzealously requires Arbitrary1. newtype MyCompose f g a = MyCompose { getMyCompose :: f (g a) }   deriving (Eq, Ord, Show, Functor, Num, Enum, Bounded, Real, Integral, Arbitrary, Generic)