fast-digits 0.3.2.0 → 0.3.3.0

raw patch · 5 files changed

+49/−14 lines, 5 filesdep −QuickCheckPVP ok

version bump matches the API change (PVP)

Dependencies removed: QuickCheck

API changes (from Hackage documentation)

Files

• bench/Bench.hs +7/−1
• changelog.md +4/−0
• fast-digits.cabal +7/−8
• src/Data/FastDigits.hs +16/−3
• tests/Tests.hs +15/−2

@@ -2,11 +2,12 @@  module Main (main) where +import Prelude hiding (Foldable(..)) #ifdef MIN_VERSION_digits import qualified Data.Digits as D (digitsRev) #endif import Data.FastDigits (digits, undigits)-import Data.List (foldl')+import Data.Foldable import Test.Tasty.Bench (Benchmark, Benchmarkable, defaultMain, bench, bgroup, nf) #ifdef MIN_VERSION_digits import Test.Tasty.Bench (bcompare)@@ -67,4 +68,9 @@   [ benchSmth "short"  benchShort   , benchSmth "medium" benchMedium   , benchSmth "long"   benchLong++  , bgroup "undigits"+  $ map+    (\n -> bench (show (n :: Int)) $ nf (\m -> undigits m [1..m-1]) n)+    [10, 100, 1000, 10000, 100000]   ]

@@ -1,3 +1,7 @@+# 0.3.3.0++* Avoid quadratic complexity in `undigits`.+ # 0.3.2.0  * Migrate from `integer-gmp` to `ghc-bignum`.

@@ -1,5 +1,5 @@ name: fast-digits-version: 0.3.2.0+version: 0.3.3.0 license: GPL-3 license-file: LICENSE maintainer: andrew.lelechenko@gmail.com@@ -18,11 +18,11 @@   changelog.md   README.md tested-with:-  GHC ==9.0.2 GHC ==9.2.8 GHC ==9.4.5 GHC ==9.6.2+  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  source-repository head   type: git-  location: git://github.com/Bodigrim/fast-digits.git+  location: https://github.com/Bodigrim/fast-digits  library   exposed-modules:@@ -32,7 +32,7 @@   ghc-options: -Wall -O2 -Wcompat   build-depends:     base >=4.15 && <5,-    ghc-bignum <1.4,+    ghc-bignum <1.5,     fast-digits-internal  library fast-digits-internal@@ -52,10 +52,9 @@   ghc-options: -Wall -Wcompat   build-depends:     base,-    tasty <1.5,-    tasty-quickcheck <0.11,+    tasty <1.6,+    tasty-quickcheck <0.12,     tasty-smallcheck <0.9,-    QuickCheck <2.15,     smallcheck <1.3,     -- digits,     fast-digits,@@ -71,4 +70,4 @@     base,     -- digits,     fast-digits,-    tasty-bench >= 0.2.4 && <0.4+    tasty-bench >= 0.4 && <0.6

@@ -145,9 +145,22 @@          => a       -- ^ The base to use          -> [b]     -- ^ The list of digits to convert          -> Integer-undigits base' = foldr (\d acc -> acc * base + toInteger d) 0-  where-    base = toInteger base'+undigits base xs+  | length xs < 700 = undigitsSmall (toInteger base) xs+  | otherwise = undigitsHuge (toInteger base) xs {-# SPECIALIZE undigits :: Word    -> [Word]    -> Integer #-} {-# SPECIALIZE undigits :: Int     -> [Int]     -> Integer #-} {-# SPECIALIZE undigits :: Integer -> [Integer] -> Integer #-}++undigitsSmall :: Integral b => Integer -> [b] -> Integer+undigitsSmall base = foldr (\d acc -> acc * base + toInteger d) 0++undigitsHuge :: Integral b => Integer -> [b] -> Integer+undigitsHuge !_ [] = 0+undigitsHuge base (x : xs) = go (toInteger x) 1 base xs+  where+    go acc power poweredBase rest = case splitAt power rest of+      ([], _) -> acc+      (p : pref, rest') -> go acc' (power * 2) (poweredBase ^ (2 :: Int)) rest'+        where+          acc' = acc + poweredBase * go (toInteger p) 1 base pref

@@ -8,6 +8,10 @@ import Test.Tasty.SmallCheck as SC (testProperty) import Test.Tasty.QuickCheck as QC (Positive(..), NonNegative(..), Property, (==>), (===), testProperty) +#if MIN_VERSION_base(4,19,0)+import Data.List (unsnoc)+#endif+ #ifdef MIN_VERSION_digits import qualified Data.Digits as D (digitsRev, unDigits) #endif@@ -70,11 +74,15 @@ -- Last digit is not 0 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)+  case unsnoc (digits base n) of+    Nothing -> False+    Just (_, d) -> d /= 0  sProperty5 :: SC.Positive Int -> SC.Positive Integer -> Bool sProperty5 (SC.Positive base) (SC.Positive n) = base == 1 ||-  ((/= 0) $ last $ digits base n)+  case unsnoc (digits base n) of+    Nothing -> False+    Just (_, d) -> d /= 0  #ifdef MIN_VERSION_digits -- digits 2 == digitsD 2@@ -140,3 +148,8 @@  main :: IO () main = defaultMain testSuite++#if !MIN_VERSION_base(4,19,0)+unsnoc :: [a] -> Maybe ([a], a)+unsnoc = foldr (\x -> Just . maybe ([], x) (\(~(a, b)) -> (x : a, b))) Nothing+#endif