fast-digits 0.1.0.0 → 0.2.0.0

raw patch · 4 files changed

+159/−69 lines, 4 filesdep ~basedep ~integer-gmpPVP ok

version bump matches the API change (PVP)

Dependency ranges changed: base, integer-gmp

API changes (from Hackage documentation)

Files

• fast-digits.cabal +6/−5
• src/Data/FastDigits.hs +71/−50
• src/Data/FastDigits/Internal.hs +51/−0
• tests/Tests.hs +31/−14

@@ -1,9 +1,9 @@ name:                fast-digits-version:             0.1.0.0+version:             0.2.0.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 30 times faster.+                     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@@ -18,9 +18,10 @@   location: git://github.com/Bodigrim/fast-digits.git  library-  exposed-modules:     Data.FastDigits-  build-depends:         base < 5-                       , integer-gmp+  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

@@ -5,11 +5,10 @@ License     : GPL-3 Maintainer  : andrew.lelechenko@gmail.com Stability   : experimental-Portability : POSIX  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 30 times faster.+For small bases and long numbers it may be up to 40 times faster. -}  {-# LANGUAGE MagicHash     #-}@@ -17,84 +16,106 @@  {-# 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--ti :: Integral a => a -> Integer-ti = toInteger--fi :: Num a => Integer -> a-fi = fromInteger-+import GHC.Integer.GMP.Internals+import GHC.Natural+import Unsafe.Coerce+import Data.FastDigits.Internal -digitsInteger :: Integer -> Integer -> [Int]-digitsInteger base = f+digitsNatural :: GmpLimb# -> BigNat -> [Word]+digitsNatural base = f   where-    f 0 = []-    f n = let (# q, r #) = n `quotRemInteger` base in fi r : f q+    f n = if n == zeroBigNat+      then []+      else let (# q, r #) = n `quotRemBigNatWord` base in W# r : f q -digitsInt :: Int# -> Int -> [Int]-digitsInt base (I# m) = f m+digitsWord :: Word# -> Word# -> [Word]+digitsWord 2## = g   where-    f :: Int# -> [Int]-    f 0# = []-    f n = let (# q, r #) = n `quotRemInt#` base in (I# r) : f q-+    g :: Word# -> [Word]+    g 0## = []+    g n = W# (n `and#` 1##) : g (n `uncheckedShiftRL#` 1#)+digitsWord base = f+  where+    f :: Word# -> [Word]+    f 0## = []+    f n = let (# q, r #) = n `quotRemWord#` base in W# r : f q -digitsInteger' :: Int -> Int -> Integer -> Integer -> [Int]-digitsInteger' power (I# base) poweredBase = f+-- | For a given base and expected length of list of digits+--   return the list of digits and padding till expected length.+digitsWordL :: Word# -> Word# -> Word# -> (# [Word], Word# #)+digitsWordL 2## power = g   where-    f :: Integer -> [Int]-    f n = fr ++ (if q == 0 then [] else replicate (power - length fr) 0 ++ f q)+    g :: Word# -> (# [Word], Word# #)+    g 0## = (# [], power #)+    g n = (# W# (n `and#` 1##) : fq, lq `minusWord#` 1## #)       where-        (# q, r #) = n `quotRemInteger` poweredBase-        fr = digitsInt base (fi r)+        (# fq, lq #) = g (n `uncheckedShiftRL#` 1#)+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 +-- | 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' base power poweredBase = f+  where+    f :: BigNat -> [Word]+    f n = let (# q, r #) = n `quotRemBigNatWord` poweredBase in+      if q == zeroBigNat+        then digitsWord base r+        else let (# fr, lr #) = digitsWordL base power r in+          fr ++ replicate (I# (unsafeCoerce# lr)) 0 ++ f q -selectPower :: Int -> (Int, Int)-selectPower base = if poweredBase > 0-    then (power, poweredBase)-    else (power - 1, base ^ (power - 1))+-- | 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   where-    power :: Int-    power = floor $ logBase (fi $ ti base) (fi $ ti $ (maxBound :: Int))-    poweredBase :: Int-    poweredBase = base ^ power+    (# power, poweredBase #) = selectPower base --- | Return digits of a non-negative integer in reverse order. E. g.,+-- | Return digits of a non-negative number in reverse order.+--   Throw an error if number is negative or base is below 2. -- --   > digits 10 123 = [3, 2, 1] --   > digits 10 0   = []------ Throw an error if number is negative or base is below 2. digits   :: Int     -- ^ The base to use-  -> Integer -- ^ The integer to convert-  -> [Int]-digits base@(I# base') n+  -> Integer -- ^ The number to convert+  -> [Int]   -- ^ Digits in reverse order+digits base n   | base < 2  = error "Base must be > 1"   | n < 0     = error "Number must be non-negative"-  | n < ti (maxBound :: Int) = digitsInt base' (fi n)-  | otherwise = if power == 1-                  then digitsInteger (ti base) n-                  else digitsInteger' power base (ti poweredBase) n-  where-    (power, poweredBase) = selectPower base+  | otherwise = unsafeCoerce+              $ digitsUnsigned (unsafeCoerce base) (unsafeCoerce n)  -- | Return an integer, built from given digits in reverse order.---   Condition 0 <= digit < base is not checked.+--   Condition 0 ≤ digit < base is not checked. undigits :: (Integral a, Integral b)          => a       -- ^ The base to use          -> [b]     -- ^ The list of digits to convert          -> Integer-undigits base' = foldr (\d acc -> acc * base + ti d) 0+undigits base' = foldr (\d acc -> acc * base + toInteger d) 0   where-    base = ti base'-{-# SPECIALIZE undigits :: Int -> [Int] -> Integer #-}+    base = toInteger base'+{-# SPECIALIZE undigits :: Word    -> [Word]    -> Integer #-}+{-# SPECIALIZE undigits :: Int     -> [Int]     -> Integer #-} {-# SPECIALIZE undigits :: Integer -> [Integer] -> Integer #-}

@@ -0,0 +1,51 @@+{-|+Module      : Data.FastDigits.Internal+Copyright   : (c) Andrew Lelechenko, 2015+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++-- | 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

@@ -13,6 +13,7 @@ import qualified Data.Digits as D  import Data.FastDigits+import Data.FastDigits.Internal  instance (Num a, Ord a, Arbitrary a) => Arbitrary (Positive a) where   arbitrary =@@ -102,22 +103,38 @@   where     n = toInteger a * toInteger (maxBound :: Int) + toInteger b +qProperty8 :: Positive Int -> QC.Property+qProperty8 (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 ||+  base ^ power == poweredBase && poweredBase > maxBound `div` base+  where+    base = fromIntegral $ toInteger base'+    (power, poweredBase) = selectPower' base+ testSuite :: TestTree testSuite = testGroup "digits"-  [ QC.testProperty "undigits base . digits base == id" qProperty1-  , SC.testProperty "undigits base . digits base == id" sProperty1-  , QC.testProperty "digits == digitsD" qProperty2-  , SC.testProperty "digits == digitsD" sProperty2-  , QC.testProperty "digits 10 == digits10" qProperty3-  , SC.testProperty "digits 10 == digits10" sProperty3-  , QC.testProperty "All digits are between 0 and base - 1" qProperty4-  , SC.testProperty "All digits are between 0 and base - 1" sProperty4-  , QC.testProperty "Last digit is not 0" qProperty5-  , SC.testProperty "Last digit is not 0" sProperty5-  , QC.testProperty "digits 2 == digitsD 2" qProperty6-  , SC.testProperty "digits 2 == digitsD 2" sProperty6-  , QC.testProperty "digits 2 == digitsD 2 on integers of special form" qProperty7-  , SC.testProperty "digits 2 == digitsD 2 on integers of special form" sProperty7+  [ SC.testProperty "S undigits base . digits base == id" sProperty1+  , QC.testProperty "Q undigits base . digits base == id" qProperty1+  , SC.testProperty "S digits == digitsD" sProperty2+  , QC.testProperty "Q digits == digitsD" qProperty2+  , 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+  , 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+  , SC.testProperty "S selectPower is correct" sProperty8+  , QC.testProperty "Q selectPower is correct" qProperty8   ]  main :: IO ()