integer-roots 1.0.3.0 → 1.0.4.0
raw patch · 9 files changed
+168/−116 lines, 9 filesdep +QuickCheckdep ~ghc-bignumPVP ok
version bump matches the API change (PVP)
Dependencies added: QuickCheck
Dependency ranges changed: ghc-bignum
API changes (from Hackage documentation)
Files
- Math/NumberTheory/Roots/Cubes.hs +25/−29
- Math/NumberTheory/Roots/Fourth.hs +22/−26
- Math/NumberTheory/Roots/General.hs +14/−13
- Math/NumberTheory/Roots/Squares.hs +48/−40
- Math/NumberTheory/Roots/Squares/Internal.hs +2/−2
- changelog.md +4/−0
- integer-roots.cabal +6/−3
- test-suite/Math/NumberTheory/Roots/SquaresTests.hs +45/−3
- test-suite/Math/NumberTheory/TestUtils.hs +2/−0
Math/NumberTheory/Roots/Cubes.hs view
@@ -10,6 +10,7 @@ {-# LANGUAGE BangPatterns #-} {-# LANGUAGE CPP #-} {-# LANGUAGE MagicHash #-}+{- HLINT ignore "Use fewer imports" -} module Math.NumberTheory.Roots.Cubes ( integerCubeRoot@@ -47,11 +48,10 @@ -- [1,2,2] -- >>> map integerCubeRoot [-7, -8, -9] -- [-2,-2,-3]-{-# SPECIALISE integerCubeRoot :: Int -> Int,- Word -> Word,- Integer -> Integer,- Natural -> Natural- #-}+{-# SPECIALISE integerCubeRoot :: Int -> Int #-}+{-# SPECIALISE integerCubeRoot :: Word -> Word #-}+{-# SPECIALISE integerCubeRoot :: Integer -> Integer #-}+{-# SPECIALISE integerCubeRoot :: Natural -> Natural #-} integerCubeRoot :: Integral a => a -> a integerCubeRoot 0 = 0 integerCubeRoot n@@ -61,7 +61,7 @@ r = if m < 0 then negate . fromInteger $ integerCubeRoot' (negate $ fromIntegral n) else negate (integerCubeRoot' m)- in if r*r*r == n then r else (r-1)+ in if r*r*r == n then r else r - 1 -- | Calculate the integer cube root of a nonnegative integer @n@, -- that is, the largest integer @r@ such that @r^3 <= n@.@@ -81,11 +81,10 @@ -- -- >>> map exactCubeRoot [-9, -8, -7, 7, 8, 9] -- [Nothing,Just (-2),Nothing,Nothing,Just 2,Nothing]-{-# SPECIALISE exactCubeRoot :: Int -> Maybe Int,- Word -> Maybe Word,- Integer -> Maybe Integer,- Natural -> Maybe Natural- #-}+{-# SPECIALISE exactCubeRoot :: Int -> Maybe Int #-}+{-# SPECIALISE exactCubeRoot :: Word -> Maybe Word #-}+{-# SPECIALISE exactCubeRoot :: Integer -> Maybe Integer #-}+{-# SPECIALISE exactCubeRoot :: Natural -> Maybe Natural #-} exactCubeRoot :: Integral a => a -> Maybe a exactCubeRoot 0 = Just 0 exactCubeRoot n@@ -103,11 +102,10 @@ -- -- >>> map isCube [-9, -8, -7, 7, 8, 9] -- [False,True,False,False,True,False]-{-# SPECIALISE isCube :: Int -> Bool,- Word -> Bool,- Integer -> Bool,- Natural -> Bool- #-}+{-# SPECIALISE isCube :: Int -> Bool #-}+{-# SPECIALISE isCube :: Word -> Bool #-}+{-# SPECIALISE isCube :: Integer -> Bool #-}+{-# SPECIALISE isCube :: Natural -> Bool #-} isCube :: Integral a => a -> Bool isCube 0 = True isCube n@@ -120,14 +118,13 @@ -- | Test whether a nonnegative integer is a cube. -- Before 'integerCubeRoot' is calculated, a few tests -- of remainders modulo small primes weed out most non-cubes.--- For testing many numbers, most of which aren't cubes,+-- On average, assuming that the majority of inputs aren't cubes, -- this is much faster than @let r = cubeRoot n in r*r*r == n@. -- The condition @n >= 0@ is /not/ checked.-{-# SPECIALISE isCube' :: Int -> Bool,- Word -> Bool,- Integer -> Bool,- Natural -> Bool- #-}+{-# SPECIALISE isCube' :: Int -> Bool #-}+{-# SPECIALISE isCube' :: Word -> Bool #-}+{-# SPECIALISE isCube' :: Integer -> Bool #-}+{-# SPECIALISE isCube' :: Natural -> Bool #-} isCube' :: Integral a => a -> Bool isCube' !n = isPossibleCube n && (r*r*r == n)@@ -137,11 +134,10 @@ -- | Test whether a nonnegative number is possibly a cube. -- Only about 0.08% of all numbers pass this test. -- The precondition @n >= 0@ is /not/ checked.-{-# SPECIALISE isPossibleCube :: Int -> Bool,- Word -> Bool,- Integer -> Bool,- Natural -> Bool- #-}+{-# SPECIALISE isPossibleCube :: Int -> Bool #-}+{-# SPECIALISE isPossibleCube :: Word -> Bool #-}+{-# SPECIALISE isPossibleCube :: Integer -> Bool #-}+{-# SPECIALISE isPossibleCube :: Natural -> Bool #-} isPossibleCube :: Integral a => a -> Bool isPossibleCube n' = indexBitSet mask512 (fromInteger (n .&. 511))@@ -182,7 +178,7 @@ | c < w && e < w && c < e = r+1 | otherwise = r where- r = truncate ((fromIntegral w) ** (1/3) :: Double)+ r = truncate (fromIntegral w ** (1/3) :: Double) c = r*r*r d = 3*r*(r+1) e = c+d@@ -212,7 +208,7 @@ appCuRt (IS i#) = case double2Int# (int2Double# i# **## (1.0## /## 3.0##)) of r# -> IS r# appCuRt n@(IP bn#)- | isTrue# ((bigNatSize# bn#) <# thresh#) =+ | isTrue# (bigNatSize# bn# <# thresh#) = floor (fromInteger n ** (1.0/3.0) :: Double) | otherwise = case integerLog2# n of #ifdef MIN_VERSION_integer_gmp
Math/NumberTheory/Roots/Fourth.hs view
@@ -9,6 +9,7 @@ {-# LANGUAGE CPP #-} {-# LANGUAGE MagicHash #-}+{- HLINT ignore "Use fewer imports" -} module Math.NumberTheory.Roots.Fourth ( integerFourthRoot@@ -41,11 +42,10 @@ -- | Calculate the integer fourth root of a nonnegative number, -- that is, the largest integer @r@ with @r^4 <= n@. -- Throws an error on negaitve input.-{-# SPECIALISE integerFourthRoot :: Int -> Int,- Word -> Word,- Integer -> Integer,- Natural -> Natural- #-}+{-# SPECIALISE integerFourthRoot :: Int -> Int #-}+{-# SPECIALISE integerFourthRoot :: Word -> Word #-}+{-# SPECIALISE integerFourthRoot :: Integer -> Integer #-}+{-# SPECIALISE integerFourthRoot :: Natural -> Natural #-} integerFourthRoot :: Integral a => a -> a integerFourthRoot n | n < 0 = error "integerFourthRoot: negative argument"@@ -66,11 +66,10 @@ -- | Returns @Nothing@ if @n@ is not a fourth power, -- @Just r@ if @n == r^4@ and @r >= 0@.-{-# SPECIALISE exactFourthRoot :: Int -> Maybe Int,- Word -> Maybe Word,- Integer -> Maybe Integer,- Natural -> Maybe Natural- #-}+{-# SPECIALISE exactFourthRoot :: Int -> Maybe Int #-}+{-# SPECIALISE exactFourthRoot :: Word -> Maybe Word #-}+{-# SPECIALISE exactFourthRoot :: Integer -> Maybe Integer #-}+{-# SPECIALISE exactFourthRoot :: Natural -> Maybe Natural #-} exactFourthRoot :: Integral a => a -> Maybe a exactFourthRoot 0 = Just 0 exactFourthRoot n@@ -84,11 +83,10 @@ -- | Test whether an integer is a fourth power. -- First nonnegativity is checked, then the unchecked -- test is called.-{-# SPECIALISE isFourthPower :: Int -> Bool,- Word -> Bool,- Integer -> Bool,- Natural -> Bool- #-}+{-# SPECIALISE isFourthPower :: Int -> Bool #-}+{-# SPECIALISE isFourthPower :: Word -> Bool #-}+{-# SPECIALISE isFourthPower :: Integer -> Bool #-}+{-# SPECIALISE isFourthPower :: Natural -> Bool #-} isFourthPower :: Integral a => a -> Bool isFourthPower 0 = True isFourthPower n = n > 0 && isFourthPower' n@@ -97,11 +95,10 @@ -- The condition is /not/ checked. If a number passes the -- 'isPossibleFourthPower' test, its integer fourth root -- is calculated.-{-# SPECIALISE isFourthPower' :: Int -> Bool,- Word -> Bool,- Integer -> Bool,- Natural -> Bool- #-}+{-# SPECIALISE isFourthPower' :: Int -> Bool #-}+{-# SPECIALISE isFourthPower' :: Word -> Bool #-}+{-# SPECIALISE isFourthPower' :: Integer -> Bool #-}+{-# SPECIALISE isFourthPower' :: Natural -> Bool #-} isFourthPower' :: Integral a => a -> Bool isFourthPower' n = isPossibleFourthPower n && r2*r2 == n where@@ -111,11 +108,10 @@ -- | Test whether a nonnegative number is a possible fourth power. -- The condition is /not/ checked. -- This eliminates about 99.958% of numbers.-{-# SPECIALISE isPossibleFourthPower :: Int -> Bool,- Word -> Bool,- Integer -> Bool,- Natural -> Bool- #-}+{-# SPECIALISE isPossibleFourthPower :: Int -> Bool #-}+{-# SPECIALISE isPossibleFourthPower :: Word -> Bool #-}+{-# SPECIALISE isPossibleFourthPower :: Integer -> Bool #-}+{-# SPECIALISE isPossibleFourthPower :: Natural -> Bool #-} isPossibleFourthPower :: Integral a => a -> Bool isPossibleFourthPower n' = indexBitSet mask256 (fromInteger (n .&. 255))@@ -144,7 +140,7 @@ appBiSqrt :: Integer -> Integer appBiSqrt (IS i#) = IS (double2Int# (sqrtDouble# (sqrtDouble# (int2Double# i#)))) appBiSqrt n@(IP bn#)- | isTrue# ((bigNatSize# bn#) <# thresh#) =+ | isTrue# (bigNatSize# bn# <# thresh#) = floor (sqrt . sqrt $ fromInteger n :: Double) | otherwise = case integerLog2# n of #ifdef MIN_VERSION_integer_gmp
Math/NumberTheory/Roots/General.hs view
@@ -12,6 +12,8 @@ {-# LANGUAGE CPP #-} {-# LANGUAGE MagicHash #-} {-# LANGUAGE ViewPatterns #-}+{- HLINT ignore "Use list comprehension" -}+{- HLINT ignore "Use fewer imports" -} module Math.NumberTheory.Roots.General ( integerRoot@@ -68,17 +70,16 @@ -- -5 -- >>> integerRoot 1 5 -- 5-{-# SPECIALISE integerRoot :: Int -> Int -> Int,- Int -> Word -> Word,- Int -> Integer -> Integer,- Int -> Natural -> Natural,- Word -> Int -> Int,- Word -> Word -> Word,- Word -> Integer -> Integer,- Word -> Natural -> Natural,- Integer -> Integer -> Integer,- Natural -> Natural -> Natural- #-}+{-# SPECIALISE integerRoot :: Int -> Int -> Int #-}+{-# SPECIALISE integerRoot :: Int -> Word -> Word #-}+{-# SPECIALISE integerRoot :: Int -> Integer -> Integer #-}+{-# SPECIALISE integerRoot :: Int -> Natural -> Natural #-}+{-# SPECIALISE integerRoot :: Word -> Int -> Int #-}+{-# SPECIALISE integerRoot :: Word -> Word -> Word #-}+{-# SPECIALISE integerRoot :: Word -> Integer -> Integer #-}+{-# SPECIALISE integerRoot :: Word -> Natural -> Natural #-}+{-# SPECIALISE integerRoot :: Integer -> Integer -> Integer #-}+{-# SPECIALISE integerRoot :: Natural -> Natural -> Natural #-} integerRoot :: (Integral a, Integral b) => b -> a -> a integerRoot 1 n = n integerRoot 2 n = P2.integerSquareRoot n@@ -89,7 +90,7 @@ | n < 0 && even k = error "integerRoot: negative radicand for even exponent" | n < 0 = let r = negate . fromInteger . integerRoot k . negate $ fromIntegral n- in if r^k == n then r else (r-1)+ in if r^k == n then r else r - 1 | n == 0 = 0 | n < 31 = 1 | kTooLarge = 1@@ -332,7 +333,7 @@ #ifdef MIN_VERSION_integer_gmp maxExp = (W# (int2Word# (integerLog2# n))) `quot` spBEx #else- maxExp = (W# (integerLog2# n)) `quot` spBEx+ maxExp = W# (integerLog2# n) `quot` spBEx #endif divs = divisorsTo maxExp e go [] = (foldl' (*) n [p^ex | (p,ex) <- pws], 1)
Math/NumberTheory/Roots/Squares.hs view
@@ -24,6 +24,8 @@ ) where import Data.Bits (finiteBitSize, (.&.))+import Data.Int (Int64)+import Data.Word (Word64) import GHC.Exts (Ptr(..)) import Numeric.Natural (Natural) @@ -40,11 +42,12 @@ -- 10 -- >>> integerSquareRoot 101 -- 10-{-# SPECIALISE integerSquareRoot :: Int -> Int,- Word -> Word,- Integer -> Integer,- Natural -> Natural- #-}+{-# SPECIALISE integerSquareRoot :: Int -> Int #-}+{-# SPECIALISE integerSquareRoot :: Word -> Word #-}+{-# SPECIALISE integerSquareRoot :: Int64 -> Int64 #-}+{-# SPECIALISE integerSquareRoot :: Word64 -> Word64 #-}+{-# SPECIALISE integerSquareRoot :: Integer -> Integer #-}+{-# SPECIALISE integerSquareRoot :: Natural -> Natural #-} integerSquareRoot :: Integral a => a -> a integerSquareRoot n | n < 0 = error "integerSquareRoot: negative argument"@@ -56,6 +59,8 @@ {-# RULES "integerSquareRoot'/Int" integerSquareRoot' = isqrtInt' "integerSquareRoot'/Word" integerSquareRoot' = isqrtWord+"integerSquareRoot'/Int64" integerSquareRoot' = isqrtInt64'+"integerSquareRoot'/Word64" integerSquareRoot' = isqrtWord64 "integerSquareRoot'/Integer" integerSquareRoot' = isqrtInteger "integerSquareRoot'/Natural" integerSquareRoot' = fromInteger . isqrtInteger . toInteger #-}@@ -74,12 +79,10 @@ -- (10,0) -- >>> integerSquareRootRem 101 -- (10,1)-{-# SPECIALISE integerSquareRootRem ::- Int -> (Int, Int),- Word -> (Word, Word),- Integer -> (Integer, Integer),- Natural -> (Natural, Natural)- #-}+{-# SPECIALISE integerSquareRootRem :: Int -> (Int, Int) #-}+{-# SPECIALISE integerSquareRootRem :: Word -> (Word, Word) #-}+{-# SPECIALISE integerSquareRootRem :: Integer -> (Integer, Integer) #-}+{-# SPECIALISE integerSquareRootRem :: Natural -> (Natural, Natural) #-} integerSquareRootRem :: Integral a => a -> (a, a) integerSquareRootRem n | n < 0 = error "integerSquareRootRem: negative argument"@@ -103,11 +106,10 @@ -- -- >>> map exactSquareRoot [-100, 99, 100, 101] -- [Nothing,Nothing,Just 10,Nothing]-{-# SPECIALISE exactSquareRoot :: Int -> Maybe Int,- Word -> Maybe Word,- Integer -> Maybe Integer,- Natural -> Maybe Natural- #-}+{-# SPECIALISE exactSquareRoot :: Int -> Maybe Int #-}+{-# SPECIALISE exactSquareRoot :: Word -> Maybe Word #-}+{-# SPECIALISE exactSquareRoot :: Integer -> Maybe Integer #-}+{-# SPECIALISE exactSquareRoot :: Natural -> Maybe Natural #-} exactSquareRoot :: Integral a => a -> Maybe a exactSquareRoot n | n >= 0@@ -119,25 +121,23 @@ -- -- >>> map isSquare [-100, 99, 100, 101] -- [False,False,True,False]-{-# SPECIALISE isSquare :: Int -> Bool,- Word -> Bool,- Integer -> Bool,- Natural -> Bool- #-}+{-# SPECIALISE isSquare :: Int -> Bool #-}+{-# SPECIALISE isSquare :: Word -> Bool #-}+{-# SPECIALISE isSquare :: Integer -> Bool #-}+{-# SPECIALISE isSquare :: Natural -> Bool #-} isSquare :: Integral a => a -> Bool isSquare n = n >= 0 && isSquare' n -- | Test whether the input (a non-negative number) @n@ is a square.--- The same as 'isSquare', but without the negativity test.--- Faster if many known positive numbers are tested.+-- The same as 'isSquare', but without the negativity test,+-- so marginally faster. -- -- The precondition @n >= 0@ is not tested, passing negative -- arguments may cause any kind of havoc.-{-# SPECIALISE isSquare' :: Int -> Bool,- Word -> Bool,- Integer -> Bool,- Natural -> Bool- #-}+{-# SPECIALISE isSquare' :: Int -> Bool #-}+{-# SPECIALISE isSquare' :: Word -> Bool #-}+{-# SPECIALISE isSquare' :: Integer -> Bool #-}+{-# SPECIALISE isSquare' :: Natural -> Bool #-} isSquare' :: Integral a => a -> Bool isSquare' n | isPossibleSquare n@@ -152,11 +152,10 @@ -- easily without division and eliminates about 82% of all numbers). -- After that, the remainders modulo 9, 25, 7, 11 and 13 are tested -- to eliminate altogether about 99.436% of all numbers.-{-# SPECIALISE isPossibleSquare :: Int -> Bool,- Word -> Bool,- Integer -> Bool,- Natural -> Bool- #-}+{-# SPECIALISE isPossibleSquare :: Int -> Bool #-}+{-# SPECIALISE isPossibleSquare :: Word -> Bool #-}+{-# SPECIALISE isPossibleSquare :: Integer -> Bool #-}+{-# SPECIALISE isPossibleSquare :: Natural -> Bool #-} isPossibleSquare :: Integral a => a -> Bool isPossibleSquare n' = indexBitSet mask256 (fromInteger (n .&. 255))@@ -214,14 +213,13 @@ | otherwise = r where !r = (truncate :: Double -> Int) . sqrt $ fromIntegral n--- With -O2, that should be translated to the below-{--isqrtInt' n@(I# i#)- | r# *# r# ># i# = I# (r# -# 1#)- | otherwise = I# r#++isqrtInt64' :: Int64 -> Int64+isqrtInt64' n+ | n < r*r = r-1+ | otherwise = r where- !r# = double2Int# (sqrtDouble# (int2Double# i#))--}+ !r = (truncate :: Double -> Int64) . sqrt $ fromIntegral n -- Same for Word. isqrtWord :: Word -> Word@@ -233,6 +231,16 @@ | otherwise = r where !r = (fromIntegral :: Int -> Word) . (truncate :: Double -> Int) . sqrt $ fromIntegral n++isqrtWord64 :: Word64 -> Word64+isqrtWord64 n+ | n < (r*r)+ -- Double interprets values near maxBound as 2^64+ || r == 4294967296+ = r-1+ | otherwise = r+ where+ !r = (fromIntegral :: Int64 -> Word64) . (truncate :: Double -> Int64) . sqrt $ fromIntegral n {-# INLINE isqrtInteger #-} isqrtInteger :: Integer -> Integer
Math/NumberTheory/Roots/Squares/Internal.hs view
@@ -6,9 +6,9 @@ -- -- Internal functions dealing with square roots. End-users should not import this module. -{-# LANGUAGE BangPatterns #-} {-# LANGUAGE CPP #-} {-# LANGUAGE MagicHash #-}+{- HLINT ignore "Use fewer imports" -} module Math.NumberTheory.Roots.Squares.Internal ( karatsubaSqrt@@ -60,7 +60,7 @@ appSqrt :: Integer -> Integer appSqrt (IS i#) = IS (double2Int# (sqrtDouble# (int2Double# i#))) appSqrt n@(IP bn#)- | isTrue# ((bigNatSize# bn#) <# thresh#) =+ | isTrue# (bigNatSize# bn# <# thresh#) = floor (sqrt $ fromInteger n :: Double) | otherwise = case integerLog2# n of #ifdef MIN_VERSION_integer_gmp
changelog.md view
@@ -1,3 +1,7 @@+# 1.0.4.0++* Add rewrite rules for `integerSquareRoot` of `Int64` and `Word64`.+ # 1.0.3.0 * Add a rewrite rule for `integerSquareRoot` of `Natural`.
integer-roots.cabal view
@@ -1,5 +1,5 @@ name: integer-roots-version: 1.0.3.0+version: 1.0.4.0 cabal-version: >=1.10 build-type: Simple license: MIT@@ -12,7 +12,9 @@ description: Calculating integer roots and testing perfect powers of arbitrary precision. Originally part of <https://hackage.haskell.org/package/arithmoi arithmoi> package. category: Math, Algorithms, Number Theory author: Daniel Fischer, Andrew Lelechenko-tested-with: GHC ==8.0.2 GHC ==8.2.2 GHC ==8.4.4 GHC ==8.6.5 GHC ==8.8.4 GHC ==8.10.7 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+tested-with: GHC ==8.0.2 GHC ==8.2.2 GHC ==8.4.4 GHC ==8.6.5 GHC ==8.8.4 GHC ==8.10.7+ 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@@ -27,7 +29,7 @@ if impl(ghc < 9.0) build-depends: integer-gmp <1.2 else- build-depends: ghc-bignum < 1.4+ build-depends: ghc-bignum < 1.5 exposed-modules: Math.NumberTheory.Roots other-modules:@@ -46,6 +48,7 @@ build-depends: base >=4.9 && <5, integer-roots,+ QuickCheck, smallcheck >=1.2 && <1.3, tasty >=0.10, tasty-hunit >=0.9 && <0.11,
test-suite/Math/NumberTheory/Roots/SquaresTests.hs view
@@ -14,6 +14,9 @@ ) where import Data.Bits+import Data.Int (Int64)+import Data.Word (Word64)+import Numeric.Natural (Natural) import Test.Tasty import Test.Tasty.HUnit @@ -35,14 +38,23 @@ integerSquareRootProperty_Int :: NonNegative Int -> Bool integerSquareRootProperty_Int = integerSquareRootProperty +integerSquareRootProperty_Int64 :: NonNegative Int64 -> Bool+integerSquareRootProperty_Int64 = integerSquareRootProperty+ -- | Specialized to trigger 'isqrtWord'. integerSquareRootProperty_Word :: NonNegative Word -> Bool integerSquareRootProperty_Word = integerSquareRootProperty +integerSquareRootProperty_Word64 :: NonNegative Word64 -> Bool+integerSquareRootProperty_Word64 = integerSquareRootProperty+ -- | Specialized to trigger 'isqrtInteger'. integerSquareRootProperty_Integer :: NonNegative Integer -> Bool integerSquareRootProperty_Integer = integerSquareRootProperty +integerSquareRootProperty_Natural :: NonNegative Natural -> Bool+integerSquareRootProperty_Natural = integerSquareRootProperty+ -- | Check that 'integerSquareRoot' returns the largest integer @m@ with @m*m <= n@, where @n@ has form @k@^2-1. integerSquareRootProperty2 :: Integral a => Positive a -> Bool integerSquareRootProperty2 (Positive k) = n < 0@@ -55,29 +67,50 @@ integerSquareRootProperty2_Int :: Positive Int -> Bool integerSquareRootProperty2_Int = integerSquareRootProperty2 +integerSquareRootProperty2_Int64 :: Positive Int64 -> Bool+integerSquareRootProperty2_Int64 = integerSquareRootProperty2+ -- | Specialized to trigger 'isqrtWord'. integerSquareRootProperty2_Word :: Positive Word -> Bool integerSquareRootProperty2_Word = integerSquareRootProperty2 +integerSquareRootProperty2_Word64 :: Positive Word64 -> Bool+integerSquareRootProperty2_Word64 = integerSquareRootProperty2+ -- | Specialized to trigger 'isqrtInteger'. integerSquareRootProperty2_Integer :: Positive Integer -> Bool integerSquareRootProperty2_Integer = integerSquareRootProperty2 +integerSquareRootProperty2_Natural :: Positive Natural -> Bool+integerSquareRootProperty2_Natural = integerSquareRootProperty2+ -- | Check that 'integerSquareRoot' of 2^62-1 is 2^31-1, not 2^31. integerSquareRootSpecialCase1_Int :: Assertion integerSquareRootSpecialCase1_Int = assertEqual "integerSquareRoot" (integerSquareRoot (maxBound `div` 2 :: Int)) (2 ^ 31 - 1) +integerSquareRootSpecialCase1_Int64 :: Assertion+integerSquareRootSpecialCase1_Int64 =+ assertEqual "integerSquareRoot" (integerSquareRoot (maxBound `div` 2 :: Int64)) (2 ^ 31 - 1)+ -- | Check that 'integerSquareRoot' of 2^62-1 is 2^31-1, not 2^31. integerSquareRootSpecialCase1_Word :: Assertion integerSquareRootSpecialCase1_Word = assertEqual "integerSquareRoot" (integerSquareRoot (maxBound `div` 4 :: Word)) (2 ^ 31 - 1) +integerSquareRootSpecialCase1_Word64 :: Assertion+integerSquareRootSpecialCase1_Word64 =+ assertEqual "integerSquareRoot" (integerSquareRoot (maxBound `div` 4 :: Word64)) (2 ^ 31 - 1)+ -- | Check that 'integerSquareRoot' of 2^64-1 is 2^32-1, not 2^32. integerSquareRootSpecialCase2 :: Assertion integerSquareRootSpecialCase2 = assertEqual "integerSquareRoot" (integerSquareRoot (maxBound :: Word)) (2 ^ 32 - 1) +integerSquareRootSpecialCase2_Word64 :: Assertion+integerSquareRootSpecialCase2_Word64 =+ assertEqual "integerSquareRoot" (integerSquareRoot (maxBound :: Word64)) (2 ^ 32 - 1)+ -- | Check that the number 'isSquare' iff its 'integerSquareRoot' is exact. isSquareProperty :: Integral a => AnySign a -> Bool isSquareProperty (AnySign n) = (n < 0 && not t) || (n /= m * m && not t) || (n == m * m && t)@@ -97,17 +130,26 @@ [ testGroup "integerSquareRoot" $ [ testIntegralProperty "generic" integerSquareRootProperty , testSmallAndQuick "generic Int" integerSquareRootProperty_Int+ , testSmallAndQuick "generic Int64" integerSquareRootProperty_Int64 , testSmallAndQuick "generic Word" integerSquareRootProperty_Word+ , testSmallAndQuick "generic Word64" integerSquareRootProperty_Word64 , testSmallAndQuick "generic Integer" integerSquareRootProperty_Integer+ , testSmallAndQuick "generic Natural" integerSquareRootProperty_Natural , testIntegralProperty "almost square" integerSquareRootProperty2 , testSmallAndQuick "almost square Int" integerSquareRootProperty2_Int+ , testSmallAndQuick "almost square Int64" integerSquareRootProperty2_Int64 , testSmallAndQuick "almost square Word" integerSquareRootProperty2_Word+ , testSmallAndQuick "almost square Word64" integerSquareRootProperty2_Word64 , testSmallAndQuick "almost square Integer" integerSquareRootProperty2_Integer+ , testSmallAndQuick "almost square Natural" integerSquareRootProperty2_Natural ] ++ if finiteBitSize (0 :: Word) /= 64 then [] else- [ testCase "maxBound / 2 :: Int" integerSquareRootSpecialCase1_Int- , testCase "maxBound / 4 :: Word" integerSquareRootSpecialCase1_Word- , testCase "maxBound :: Word" integerSquareRootSpecialCase2+ [ testCase "maxBound / 2 :: Int" integerSquareRootSpecialCase1_Int+ , testCase "maxBound / 2 :: Int64" integerSquareRootSpecialCase1_Int64+ , testCase "maxBound / 4 :: Word" integerSquareRootSpecialCase1_Word+ , testCase "maxBound / 4 :: Word64" integerSquareRootSpecialCase1_Word64+ , testCase "maxBound :: Word" integerSquareRootSpecialCase2+ , testCase "maxBound :: Word64" integerSquareRootSpecialCase2_Word64 ] , testIntegralProperty "isSquare" isSquareProperty
test-suite/Math/NumberTheory/TestUtils.hs view
@@ -49,9 +49,11 @@ import Math.NumberTheory.TestUtils.Wrappers +#if !MIN_VERSION_QuickCheck(2,17,0) instance Arbitrary Natural where arbitrary = fromInteger <$> (arbitrary `suchThat` (>= 0)) shrink = map fromInteger . filter (>= 0) . shrink . toInteger+#endif #if !MIN_VERSION_smallcheck(1,2,0) instance Functor NonNegative where