fast-digits 0.2.1.0 → 0.3.2.0
raw patch · 9 files changed
Files
- README.md +76/−0
- Setup.hs +0/−2
- bench/Bench.hs +54/−37
- changelog.md +23/−0
- fast-digits.cabal +67/−46
- src-internal/Data/FastDigits/Internal.hs +47/−0
- src/Data/FastDigits.hs +63/−33
- src/Data/FastDigits/Internal.hs +0/−53
- tests/Tests.hs +60/−59
+ README.md view
@@ -0,0 +1,76 @@+# fast-digits [](https://hackage.haskell.org/package/fast-digits) [](http://stackage.org/lts/package/fast-digits) [](http://stackage.org/nightly/package/fast-digits)++The fastest Haskell library to split integers into digits.+It is both asymptotically (O(n<sup>1.4</sup>) vs. O(n<sup>2</sup>))+and practically (2x-40x for typical inputs)+faster than [Data.Digits](https://hackage.haskell.org/package/digits).++Here are benchmarks for GHC 8.10:++```+> cabal bench -w ghc-8.10.4+All+ short+ 2+ FastDigits: OK (3.11s)+ 12.3 ms ± 701 μs+ Data.Digits: OK (1.41s)+ 22.2 ms ± 1.8 ms, 1.81x+ 10+ FastDigits: OK (2.11s)+ 4.16 ms ± 369 μs+ Data.Digits: OK (3.74s)+ 7.40 ms ± 235 μs, 1.78x+ 100000+ FastDigits: OK (4.89s)+ 1.20 ms ± 69 μs+ Data.Digits: OK (3.96s)+ 1.95 ms ± 78 μs, 1.63x+ 1000000000+ FastDigits: OK (4.02s)+ 985 μs ± 62 μs+ Data.Digits: OK (3.15s)+ 1.54 ms ± 70 μs, 1.56x+ medium+ 2+ FastDigits: OK (3.02s)+ 1.49 ms ± 66 μs+ Data.Digits: OK (1.42s)+ 5.62 ms ± 542 μs, 3.77x+ 10+ FastDigits: OK (2.35s)+ 571 μs ± 42 μs+ Data.Digits: OK (1.77s)+ 1.76 ms ± 152 μs, 3.07x+ 100000+ FastDigits: OK (3.87s)+ 238 μs ± 19 μs+ Data.Digits: OK (3.44s)+ 419 μs ± 23 μs, 1.76x+ 1000000000+ FastDigits: OK (3.05s)+ 186 μs ± 13 μs+ Data.Digits: OK (4.42s)+ 268 μs ± 11 μs, 1.44x+ long+ 2+ FastDigits: OK (3.75s)+ 3.60 ms ± 215 μs+ Data.Digits: OK (1.89s)+ 125 ms ± 9.6 ms, 34.88x+ 10+ FastDigits: OK (2.30s)+ 2.24 ms ± 125 μs+ Data.Digits: OK (2.47s)+ 39.0 ms ± 2.0 ms, 17.40x+ 100000+ FastDigits: OK (1.93s)+ 1.88 ms ± 139 μs+ Data.Digits: OK (4.52s)+ 8.82 ms ± 533 μs, 4.70x+ 1000000000+ FastDigits: OK (1.77s)+ 1.71 ms ± 149 μs+ Data.Digits: OK (1.35s)+ 5.30 ms ± 482 μs, 3.10x+```
− Setup.hs
@@ -1,2 +0,0 @@-import Distribution.Simple-main = defaultMain
bench/Bench.hs view
@@ -1,15 +1,21 @@-module Main where--import Criterion.Main+{-# LANGUAGE CPP #-} -import qualified Data.Digits as D+module Main (main) where -import Data.FastDigits+#ifdef MIN_VERSION_digits+import qualified Data.Digits as D (digitsRev)+#endif+import Data.FastDigits (digits, undigits)+import Data.List (foldl')+import Test.Tasty.Bench (Benchmark, Benchmarkable, defaultMain, bench, bgroup, nf)+#ifdef MIN_VERSION_digits+import Test.Tasty.Bench (bcompare)+#endif +#ifdef MIN_VERSION_digits digitsD :: Int -> Integer -> [Int] digitsD base n = map fromInteger $ D.digitsRev (toInteger base) n--+#endif intNs :: Int -> Int -> [Int] intNs from len = [from, step .. maxBound]@@ -19,35 +25,46 @@ integerN :: Int -> Int -> Integer integerN from len = undigits (maxBound :: Int) (intNs from len) -integerNs :: Int -> Int -> [Integer]-integerNs llen len = map (\i -> integerN i len) [1..llen]+benchShort :: (Integer -> [Int]) -> Benchmarkable+benchShort f = flip nf 10000 $+ \len -> foldl' (+) 0 $ concatMap (f . toInteger)+ [1 :: Int, maxBound `quot` len .. maxBound]+{-# INLINE benchShort #-} -main = defaultMain [- bgroup "shortInt" [ bench "FastDigits base 2 " $ nf (map $ digits 2 . toInteger) (intNs 1 10000)- , bench "Data.Digits base 2 " $ nf (map $ digitsD 2 . toInteger) (intNs 1 10000)- , bench "FastDigits base 10 " $ nf (map $ digits 10 . toInteger) (intNs 1 10000)- , bench "Data.Digits base 10 " $ nf (map $ digitsD 10 . toInteger) (intNs 1 10000)- , bench "FastDigits base 10^5" $ nf (map $ digits (10^5) . toInteger) (intNs 1 10000)- , bench "Data.Digits base 10^5" $ nf (map $ digitsD (10^5) . toInteger) (intNs 1 10000)- , bench "FastDigits base 10^9" $ nf (map $ digits (10^9) . toInteger) (intNs 1 10000)- , bench "Data.Digits base 10^9" $ nf (map $ digitsD (10^9) . toInteger) (intNs 1 10000)- ],- bgroup "mediumInt" [ bench "FastDigits base 2 " $ nf (map $ digits 2 ) (integerNs 100 10)- , bench "Data.Digits base 2 " $ nf (map $ digitsD 2 ) (integerNs 100 10)- , bench "FastDigits base 10 " $ nf (map $ digits 10 ) (integerNs 100 10)- , bench "Data.Digits base 10 " $ nf (map $ digitsD 10 ) (integerNs 100 10)- , bench "FastDigits base 10^5" $ nf (map $ digits (10^5)) (integerNs 100 10)- , bench "Data.Digits base 10^5" $ nf (map $ digitsD (10^5)) (integerNs 100 10)- , bench "FastDigits base 10^9" $ nf (map $ digits (10^9)) (integerNs 100 10)- , bench "Data.Digits base 10^9" $ nf (map $ digitsD (10^9)) (integerNs 100 10)- ],- bgroup "longInt" [ bench "FastDigits base 2 " $ nf (digits 2 ) (integerN 1 1000)- , bench "Data.Digits base 2 " $ nf (digitsD 2 ) (integerN 1 1000)- , bench "FastDigits base 10 " $ nf (digits 10 ) (integerN 1 1000)- , bench "Data.Digits base 10 " $ nf (digitsD 10 ) (integerN 1 1000)- , bench "FastDigits base 10^5" $ nf (digits (10^5)) (integerN 1 1000)- , bench "Data.Digits base 10^5" $ nf (digitsD (10^5)) (integerN 1 1000)- , bench "FastDigits base 10^9" $ nf (digits (10^9)) (integerN 1 1000)- , bench "Data.Digits base 10^9" $ nf (digitsD (10^9)) (integerN 1 1000)- ]+benchMedium :: (Integer -> [Int]) -> Benchmarkable+benchMedium f = flip nf 100 $+ \len -> foldl' (+) 0 $ concatMap (f . flip integerN 10) [1 :: Int .. len]+{-# INLINE benchMedium #-}++benchLong :: (Integer -> [Int]) -> Benchmarkable+benchLong f = flip nf 1000 $+ \len -> foldl' (+) 0 $ f $ integerN 1 len+{-# INLINE benchLong #-}++benchBase :: ((Integer -> [Int]) -> Benchmarkable) -> String -> Int -> Benchmark+#ifdef MIN_VERSION_digits+benchBase b groupName base = bgroup (show base)+ [ bench "FastDigits" (b (digits base))+ , bcompare ("$NF == \"FastDigits\" && $(NF-1) == \"" ++ show base ++ "\" && $(NF-2) == \"" ++ groupName ++ "\"")+ $ bench "Data.Digits" (b (digitsD base))+ ]+#else+benchBase b _ base = bench (show base) (b (digits base))+#endif+{-# INLINE benchBase #-}++benchSmth :: String -> ((Integer -> [Int]) -> Benchmarkable) -> Benchmark+benchSmth name b = bgroup name $+ [ benchBase b name 2+ , benchBase b name 10+ , benchBase b name 100000+ , benchBase b name 1000000000+ ]+{-# INLINE benchSmth #-}++main :: IO ()+main = defaultMain+ [ benchSmth "short" benchShort+ , benchSmth "medium" benchMedium+ , benchSmth "long" benchLong ]
+ changelog.md view
@@ -0,0 +1,23 @@+# 0.3.2.0++* Migrate from `integer-gmp` to `ghc-bignum`.++# 0.3.1.0++* Performance improvement for decimal digits.++# 0.3.0.0++* Hide `Data.FastDigits.Internal`.++# 0.2.1.0++* Fix x32 build.++# 0.2.0.0++* Performance improvements.++# 0.1.0.0++* Initial release.
fast-digits.cabal view
@@ -1,53 +1,74 @@-name: fast-digits-version: 0.2.1.0-synopsis: The fast library for integer-to-digits conversion.-description: Convert an integer to digits and back.- Usually this library is twice as fast as "Data.Digits".- For small bases and long numbers it may be up to 40 times faster.-homepage: https://github.com/Bodigrim/fast-digits-license: GPL-3-license-file: LICENSE-author: Andrew Lelechenko-maintainer: andrew.lelechenko@gmail.com-category: Data-build-type: Simple-cabal-version: >=1.10+name: fast-digits+version: 0.3.2.0+license: GPL-3+license-file: LICENSE+maintainer: andrew.lelechenko@gmail.com+author: Andrew Lelechenko+homepage: https://github.com/Bodigrim/fast-digits+synopsis: Integer-to-digits conversion.+description:+ Convert an integer to digits and back.+ This library is both asymptotically (O(n^1.4) vs. O(n^2))+ and practically (2x-40x for typical inputs)+ faster than "Data.Digits".+category: Data+build-type: Simple+cabal-version: 2.0+extra-doc-files:+ changelog.md+ README.md+tested-with:+ GHC ==9.0.2 GHC ==9.2.8 GHC ==9.4.5 GHC ==9.6.2 source-repository head- type: git+ type: git location: git://github.com/Bodigrim/fast-digits.git library- exposed-modules: Data.FastDigits- , Data.FastDigits.Internal- build-depends: base >=4.8 && < 5- , integer-gmp >=1.0- hs-source-dirs: src- default-language: Haskell2010- ghc-options: -Wall+ exposed-modules:+ Data.FastDigits+ hs-source-dirs: src+ default-language: Haskell2010+ ghc-options: -Wall -O2 -Wcompat+ build-depends:+ base >=4.15 && <5,+ ghc-bignum <1.4,+ fast-digits-internal -test-suite tests- type: exitcode-stdio-1.0- main-is: Tests.hs- build-depends: base- , tasty- , tasty-quickcheck- , tasty-smallcheck- , QuickCheck- , smallcheck- , digits- , fast-digits- hs-source-dirs: tests- default-language: Haskell2010- ghc-options: -Wall+library fast-digits-internal+ exposed-modules:+ Data.FastDigits.Internal+ hs-source-dirs: src-internal+ default-language: Haskell2010+ ghc-options: -Wall -O2 -Wcompat+ build-depends:+ base >=4.8 && <5 -benchmark bench- type: exitcode-stdio-1.0- main-is: Bench.hs- hs-source-dirs: bench- build-depends: base- , criterion- , digits- , fast-digits- default-language: Haskell2010- ghc-options: -O2+test-suite fast-digits-tests+ type: exitcode-stdio-1.0+ main-is: Tests.hs+ hs-source-dirs: tests+ default-language: Haskell2010+ ghc-options: -Wall -Wcompat+ build-depends:+ base,+ tasty <1.5,+ tasty-quickcheck <0.11,+ tasty-smallcheck <0.9,+ QuickCheck <2.15,+ smallcheck <1.3,+ -- digits,+ fast-digits,+ fast-digits-internal++benchmark fast-digits-bench+ type: exitcode-stdio-1.0+ main-is: Bench.hs+ hs-source-dirs: bench+ default-language: Haskell2010+ ghc-options: -Wall -O2 -Wcompat+ build-depends:+ base,+ -- digits,+ fast-digits,+ tasty-bench >= 0.2.4 && <0.4
+ src-internal/Data/FastDigits/Internal.hs view
@@ -0,0 +1,47 @@+{-|+Module : Data.FastDigits.Internal+Copyright : (c) Andrew Lelechenko, 2015-2016+License : GPL-3+Maintainer : andrew.lelechenko@gmail.com++-}++{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE CPP #-}+{-# LANGUAGE MagicHash #-}+{-# LANGUAGE UnboxedTuples #-}++module Data.FastDigits.Internal+ ( selectPower+ , selectPower'+ ) where++import Data.Bits (finiteBitSize)+import GHC.Exts (Word#, Word(..), timesWord2#, plusWord#, timesWord#)++-- | Take an integer base and return (pow, base^pow),+-- where base^pow <= maxBound and pow is as large as possible.+selectPower :: Word# -> (# Word#, Word# #)+selectPower 2##+ | finiteBitSize (0 :: Word) == 64+ = (# 63##, 9223372036854775808## #)+selectPower 10##+ | finiteBitSize (0 :: Word) == 64+ = (# 19##, 10000000000000000000## #)++selectPower base = go base+ where+ go pw = case timesWord2# pw pw of+ (# 0##, pw2 #)+ -> let !(# n, pw2n #) = go pw2 in+ case timesWord2# pw pw2n of+ (# 0##, pw2n1 #) -> (#n `timesWord#` 2## `plusWord#` 1##, pw2n1 #)+ _ -> (# n `timesWord#` 2##, pw2n #)+ _ -> (# 1##, pw #)++-- | Take an integer base and return (pow, base^pow),+-- where base^pow <= maxBound and pow is as large as possible.+selectPower' :: Word -> (Word, Word)+selectPower' (W# base) = (W# power, W# poweredBase)+ where+ !(# power, poweredBase #) = selectPower base
src/Data/FastDigits.hs view
@@ -1,41 +1,38 @@ {-| Module : Data.FastDigits-Description : The fast library for integer-to-digits conversion.-Copyright : (c) Andrew Lelechenko, 2015-2016+Description : Integer-to-digits conversion.+Copyright : (c) Andrew Lelechenko, 2015-2020 License : GPL-3 Maintainer : andrew.lelechenko@gmail.com-Stability : experimental Convert an integer to digits and back.-Usually this library is twice as fast as "Data.Digits".-For small bases and long numbers it may be up to 40 times faster.+This library is both asymptotically (O(n^1.4) vs. O(n^2))+and practically (2x-40x for typical inputs)+faster than "Data.Digits". -} +{-# LANGUAGE BangPatterns #-} {-# LANGUAGE MagicHash #-} {-# LANGUAGE UnboxedTuples #-} -{-# OPTIONS_GHC -fno-warn-type-defaults #-}-{-# OPTIONS_GHC -O2 #-}-{-# OPTIONS_GHC -optc-O3 #-}- module Data.FastDigits ( digits , undigits , digitsUnsigned ) where -import GHC.Exts-import GHC.Integer.GMP.Internals-import GHC.Natural-import Unsafe.Coerce-import Data.FastDigits.Internal+import Data.Bits (finiteBitSize)+import GHC.Exts (Word#, Word(..), uncheckedShiftRL#, and#, timesWord2#, minusWord#, quotRemWord#, timesWord#, Int(..), iShiftRL#, isTrue#, word2Int#, (>#), (*#))+import Data.FastDigits.Internal (selectPower)+import GHC.Natural (Natural(..))+import GHC.Num.BigNat (BigNat(..), bigNatIsZero, bigNatQuotRemWord#, bigNatSize#, BigNat#) -digitsNatural :: GmpLimb# -> BigNat -> [Word]+digitsNatural :: Word# -> BigNat# -> [Word] digitsNatural base = f where f n- | isZeroBigNat n = []- | otherwise = let (# q, r #) = n `quotRemBigNatWord` base in+ | bigNatIsZero n = []+ | otherwise = let !(# q, r #) = n `bigNatQuotRemWord#` base in W# r : f q digitsWord :: Word# -> Word# -> [Word]@@ -44,11 +41,21 @@ g :: Word# -> [Word] g 0## = [] g n = W# (n `and#` 1##) : g (n `uncheckedShiftRL#` 1#)+digitsWord 10##+ | finiteBitSize (0 :: Word) == 64+ = f+ where+ f :: Word# -> [Word]+ f 0## = []+ f n = let !(# hi, _ #) = n `timesWord2#` 14757395258967641293## in+ let q = hi `uncheckedShiftRL#` 3# in+ let r = n `minusWord#` (q `timesWord#` 10##) in+ W# r : f q digitsWord base = f where f :: Word# -> [Word] f 0## = []- f n = let (# q, r #) = n `quotRemWord#` base in+ f n = let !(# q, r #) = n `quotRemWord#` base in W# r : f q -- | For a given base and expected length of list of digits@@ -60,39 +67,62 @@ g 0## = (# [], power #) g n = (# W# (n `and#` 1##) : fq, lq `minusWord#` 1## #) where- (# fq, lq #) = g (n `uncheckedShiftRL#` 1#)+ !(# fq, lq #) = g (n `uncheckedShiftRL#` 1#)+digitsWordL 10## power+ | finiteBitSize (0 :: Word) == 64+ = f+ where+ f :: Word# -> (# [Word], Word# #)+ f 0## = (# [], power #)+ f n = (# W# r : fq, lq `minusWord#` 1## #)+ where+ !(# hi, _ #) = n `timesWord2#` 14757395258967641293##+ q = hi `uncheckedShiftRL#` 3#+ r = n `minusWord#` (q `timesWord#` 10##)+ !(# fq, lq #) = f q digitsWordL base power = f where f :: Word# -> (# [Word], Word# #) f 0## = (# [], power #) f n = (# W# r : fq, lq `minusWord#` 1## #) where- (# q, r #) = n `quotRemWord#` base- (# fq, lq #) = f q+ !(# q, r #) = n `quotRemWord#` base+ !(# fq, lq #) = f q -- | For a given base, power and precalculated base^power -- take an integer and return the list of its digits.-digitsNatural' :: Word# -> Word# -> Word# -> BigNat -> [Word]+digitsNatural' :: Word# -> Word# -> Word# -> BigNat# -> [Word] digitsNatural' base power poweredBase = f where- f :: BigNat -> [Word]- f n = let (# q, r #) = n `quotRemBigNatWord` poweredBase in- if isZeroBigNat q+ f :: BigNat# -> [Word]+ f n = let !(# q, r #) = n `bigNatQuotRemWord#` poweredBase in+ if bigNatIsZero q then digitsWord base r- else let (# fr, lr #) = digitsWordL base power r in- fr ++ replicate (I# (unsafeCoerce# lr)) 0 ++ f q+ else let !(# fr, lr #) = digitsWordL base power r in+ fr ++ replicate (I# (word2Int# lr)) 0 ++ f q +padUpTo :: Int -> [Word] -> [Word]+padUpTo !n [] = replicate n 0+padUpTo !n (x : xs) = x : padUpTo (n - 1) xs+ -- | Return digits of a non-negative number in reverse order. digitsUnsigned :: Word -- ^ Precondition that base is ≥2 is not checked -> Natural -> [Word] digitsUnsigned (W# base) (NatS# n) = digitsWord base n-digitsUnsigned (W# base) (NatJ# n) = case power of- 1## -> digitsNatural base n- _ -> digitsNatural' base power poweredBase n+digitsUnsigned (W# base) (NatJ# n@(BN# n#))+ | halfSize <- bigNatSize# n# `iShiftRL#` 1#+ , isTrue# (halfSize ># 128#)+ = let pow = I# (word2Int# power *# halfSize) in+ let (nHi, nLo) = NatJ# n `quotRem` (NatS# poweredBase ^ (I# halfSize)) in+ padUpTo pow (digitsUnsigned (W# base) nLo) ++ digitsUnsigned (W# base) nHi+ | otherwise+ = case power of+ 1## -> digitsNatural base n#+ _ -> digitsNatural' base power poweredBase n# where- (# power, poweredBase #) = selectPower base+ !(# power, poweredBase #) = selectPower base -- | Return digits of a non-negative number in reverse order. -- Throw an error if number is negative or base is below 2.@@ -106,8 +136,8 @@ digits base n | base < 2 = error "Base must be > 1" | n < 0 = error "Number must be non-negative"- | otherwise = unsafeCoerce- $ digitsUnsigned (unsafeCoerce base) (unsafeCoerce n)+ | otherwise = map fromIntegral+ $ digitsUnsigned (fromIntegral base) (fromInteger n) -- | Return an integer, built from given digits in reverse order. -- Condition 0 ≤ digit < base is not checked.
− src/Data/FastDigits/Internal.hs
@@ -1,53 +0,0 @@-{-|-Module : Data.FastDigits.Internal-Copyright : (c) Andrew Lelechenko, 2015-2016-License : GPL-3-Maintainer : andrew.lelechenko@gmail.com-Stability : experimental---}--{-# LANGUAGE CPP #-}-{-# LANGUAGE MagicHash #-}-{-# LANGUAGE UnboxedTuples #-}--{-# OPTIONS_GHC -fno-warn-type-defaults #-}-{-# OPTIONS_GHC -O2 #-}-{-# OPTIONS_GHC -optc-O3 #-}--module Data.FastDigits.Internal- ( selectPower- , selectPower'- ) where--import GHC.Exts--#include "MachDeps.h"---- | Take an integer base and return (pow, base^pow),--- where base^pow <= maxBound and pow is as large as possible.-selectPower :: Word# -> (# Word#, Word# #)-#if WORD_SIZE_IN_BITS == 31-selectPower 2## = (# 31##, 2147483648## #)-#elif WORD_SIZE_IN_BITS == 32-selectPower 2## = (# 31##, 2147483648## #)-#else-selectPower 2## = (# 63##, 9223372036854775808## #)-#endif--selectPower base = go base- where- go pw = case timesWord2# pw pw of- (# 0##, pw2 #)- -> let (# n, pw2n #) = go pw2 in- case timesWord2# pw pw2n of- (# 0##, pw2n1 #) -> (#n `timesWord#` 2## `plusWord#` 1##, pw2n1 #)- _ -> (# n `timesWord#` 2##, pw2n #)- _ -> (# 1##, pw #)---- | Take an integer base and return (pow, base^pow),--- where base^pow <= maxBound and pow is as large as possible.-selectPower' :: Word -> (Word, Word)-selectPower' (W# base) = (W# power, W# poweredBase)- where- (# power, poweredBase #) = selectPower base
tests/Tests.hs view
@@ -1,117 +1,114 @@+{-# LANGUAGE CPP #-} {-# LANGUAGE ViewPatterns #-} -{-# OPTIONS_GHC -fno-warn-orphans #-}--module Main where--import Test.Tasty-import Test.Tasty.SmallCheck as SC-import Test.Tasty.QuickCheck as QC hiding (Positive, NonNegative)--import Test.SmallCheck.Series--import qualified Data.Digits as D--import Data.FastDigits-import Data.FastDigits.Internal+module Main (main) where -instance (Num a, Ord a, Arbitrary a) => Arbitrary (Positive a) where- arbitrary =- (Positive . abs) `fmap` (arbitrary `suchThat` (> 0))+import Test.SmallCheck.Series as SC (Positive(..), NonNegative(..))+import Test.Tasty (TestTree, testGroup, defaultMain)+import Test.Tasty.SmallCheck as SC (testProperty)+import Test.Tasty.QuickCheck as QC (Positive(..), NonNegative(..), Property, (==>), (===), testProperty) -instance (Num a, Ord a, Arbitrary a) => Arbitrary (NonNegative a) where- arbitrary =- (NonNegative . abs) `fmap` (arbitrary `suchThat` (>= 0))+#ifdef MIN_VERSION_digits+import qualified Data.Digits as D (digitsRev, unDigits)+#endif +import Data.FastDigits (digits, undigits)+import Data.FastDigits.Internal (selectPower') +#ifdef MIN_VERSION_digits digitsD :: Int -> Integer -> [Int] digitsD base n = map fromInteger $ D.digitsRev (toInteger base) n undigitsD :: Int -> [Int] -> Integer undigitsD base ns = D.unDigits (toInteger base) (map toInteger ns)+#endif digits10 :: Integer -> [Int] digits10 = reverse . map (read . (:[])) . show -largeInteger :: [Positive Int] -> Integer-largeInteger ns = read $ take 1000 $ '0' : concatMap (\(Positive n) -> show n) ns+largeInteger :: [QC.Positive Int] -> QC.NonNegative Integer+largeInteger ns = QC.NonNegative $ read $ take 1000 $ '0' : concatMap (\(QC.Positive n) -> show n) ns -- undigits base . digits base == id-qProperty1 :: Positive Int -> [Positive Int] -> QC.Property-qProperty1 (Positive base) (largeInteger -> n) = base > 1 QC.==>- undigits base (digits base n) == n+qProperty1 :: QC.Positive Int -> [QC.Positive Int] -> QC.Property+qProperty1 (QC.Positive base) (largeInteger -> QC.NonNegative n) = base /= 1 QC.==>+ undigits base (digits base n) === n -sProperty1 :: Int -> Integer -> Bool-sProperty1 base n = base <= 1 || n < 0 ||+sProperty1 :: SC.Positive Int -> SC.NonNegative Integer -> Bool+sProperty1 (SC.Positive base) (SC.NonNegative n) = base == 1 || undigits base (digits base n) == n +#ifdef MIN_VERSION_digits -- digits == digitsD-qProperty2 :: Positive Int -> [Positive Int] -> QC.Property-qProperty2 (Positive base) (largeInteger -> n) = base > 1 && n > 0QC.==>- digits base n == digitsD base n+qProperty2 :: QC.Positive Int -> [QC.Positive Int] -> QC.Property+qProperty2 (QC.Positive base) (largeInteger -> QC.NonNegative n) = base /= 1 QC.==>+ digits base n === digitsD base n -sProperty2 :: Int -> Integer -> Bool-sProperty2 base n = base <= 1 || n < 0 ||+sProperty2 :: SC.Positive Int -> SC.NonNegative Integer -> Bool+sProperty2 (SC.Positive base) (SC.NonNegative n) = base == 1 || digits base n == digitsD base n+#endif -- digits 10 == digits10-qProperty3 :: [Positive Int] -> QC.Property-qProperty3 (largeInteger -> n) = n > 0 QC.==>- digits 10 n == digits10 n+qProperty3 :: [QC.Positive Int] -> QC.Property+qProperty3 (largeInteger -> QC.NonNegative n) = n /= 0 QC.==>+ digits 10 n === digits10 n -sProperty3 :: Integer -> Bool-sProperty3 n = n <= 0 ||+sProperty3 :: SC.Positive Integer -> Bool+sProperty3 (SC.Positive n) = digits 10 n == digits10 n -- All digits are between 0 and base - 1-qProperty4 :: Positive Int -> [Positive Int] -> QC.Property-qProperty4 (Positive base) (largeInteger -> n) = base > 1 QC.==>+qProperty4 :: QC.Positive Int -> [QC.Positive Int] -> QC.Property+qProperty4 (QC.Positive base) (largeInteger -> QC.NonNegative n) = base /= 1 QC.==> all (\d -> d >= 0 && d < base) (digits base n) -sProperty4 :: Int -> Integer -> Bool-sProperty4 base n = base <= 1 || n < 0 ||+sProperty4 :: SC.Positive Int -> SC.NonNegative Integer -> Bool+sProperty4 (SC.Positive base) (SC.NonNegative n) = base == 1 || all (\d -> d >= 0 && d < base) (digits base n) -- Last digit is not 0-qProperty5 :: Positive Int -> [Positive Int] -> QC.Property-qProperty5 (Positive base) (largeInteger -> n) = base > 1 && n > 0 QC.==>+qProperty5 :: QC.Positive Int -> [QC.Positive Int] -> QC.Property+qProperty5 (QC.Positive base) (largeInteger -> QC.NonNegative n) = base /= 1 && n /= 0 QC.==> ((/= 0) $ last $ digits base n) -sProperty5 :: Int -> Integer -> Bool-sProperty5 base n = base <= 1 || n <= 0 ||+sProperty5 :: SC.Positive Int -> SC.Positive Integer -> Bool+sProperty5 (SC.Positive base) (SC.Positive n) = base == 1 || ((/= 0) $ last $ digits base n) +#ifdef MIN_VERSION_digits -- digits 2 == digitsD 2-qProperty6 :: [Positive Int] -> Bool-qProperty6 (largeInteger -> n) =- digits 2 n == digitsD 2 n+qProperty6 :: [QC.Positive Int] -> QC.Property+qProperty6 (largeInteger -> QC.NonNegative n) =+ digits 2 n === digitsD 2 n -sProperty6 :: Integer -> Bool-sProperty6 n = n < 0 ||+sProperty6 :: SC.NonNegative Integer -> Bool+sProperty6 (SC.NonNegative n) = digits 2 n == digitsD 2 n -- digits 2 == digitsD 2 on integers of special form-qProperty7 :: NonNegative Int -> NonNegative Int -> Bool-qProperty7 (NonNegative a) (NonNegative b) =- digits 2 n == digitsD 2 n+qProperty7 :: QC.NonNegative Int -> QC.NonNegative Int -> QC.Property+qProperty7 (QC.NonNegative a) (QC.NonNegative b) =+ digits 2 n === digitsD 2 n where n = toInteger a * toInteger (maxBound :: Int) + toInteger b -sProperty7 :: Int -> Int -> Bool-sProperty7 a b = a < 0 || b < 0 ||+sProperty7 :: SC.NonNegative Int -> SC.NonNegative Int -> Bool+sProperty7 (SC.NonNegative a) (SC.NonNegative b) = digits 2 n == digitsD 2 n where n = toInteger a * toInteger (maxBound :: Int) + toInteger b+#endif -qProperty8 :: Positive Int -> QC.Property-qProperty8 (Positive base') = base > 1 QC.==>+qProperty8 :: QC.Positive Int -> QC.Property+qProperty8 (QC.Positive base') = base /= 1 QC.==> base ^ power == poweredBase && poweredBase > maxBound `div` base where base = fromIntegral $ toInteger base' (power, poweredBase) = selectPower' base -sProperty8 :: Positive Int -> Bool-sProperty8 (Positive base') = base <= 1 ||+sProperty8 :: SC.Positive Int -> Bool+sProperty8 (SC.Positive base') = base == 1 || base ^ power == poweredBase && poweredBase > maxBound `div` base where base = fromIntegral $ toInteger base'@@ -121,18 +118,22 @@ testSuite = testGroup "digits" [ SC.testProperty "S undigits base . digits base == id" sProperty1 , QC.testProperty "Q undigits base . digits base == id" qProperty1+#ifdef MIN_VERSION_digits , SC.testProperty "S digits == digitsD" sProperty2 , QC.testProperty "Q digits == digitsD" qProperty2+#endif , SC.testProperty "S digits 10 == digits10" sProperty3 , QC.testProperty "Q digits 10 == digits10" qProperty3 , SC.testProperty "S All digits are between 0 and base - 1" sProperty4 , QC.testProperty "Q All digits are between 0 and base - 1" qProperty4 , SC.testProperty "S Last digit is not 0" sProperty5 , QC.testProperty "Q Last digit is not 0" qProperty5+#ifdef MIN_VERSION_digits , SC.testProperty "S digits 2 == digitsD 2" sProperty6 , QC.testProperty "Q digits 2 == digitsD 2" qProperty6 , SC.testProperty "S digits 2 == digitsD 2 on integers of special form" sProperty7 , QC.testProperty "Q digits 2 == digitsD 2 on integers of special form" qProperty7+#endif , SC.testProperty "S selectPower is correct" sProperty8 , QC.testProperty "Q selectPower is correct" qProperty8 ]