exact-combinatorics 0.2.0.4 → 0.2.0.7
raw patch · 5 files changed
+20/−18 lines, 5 files
Files
- LICENSE +1/−1
- README +4/−2
- exact-combinatorics.cabal +4/−4
- src/Math/Combinatorics/Exact/Binomial.hs +3/−3
- src/Math/Combinatorics/Exact/Factorial.hs +8/−8
LICENSE view
@@ -1,4 +1,4 @@-Copyright (c) 2011, 2012, wren ng thornton.+Copyright (c) 2011--2013, wren ng thornton. ALL RIGHTS RESERVED. Redistribution and use in source and binary forms, with or without
README view
@@ -17,9 +17,11 @@ $> runhaskell Setup.hs build $> runhaskell Setup.hs test $> runhaskell Setup.hs haddock --hyperlink-source- $> runhaskell Setup.hs install+ $> runhaskell Setup.hs copy+ $> runhaskell Setup.hs register -The test step is optional and currently does nothing.+The test step is optional and currently does nothing. The Haddock+step is also optional. Portability
exact-combinatorics.cabal view
@@ -1,5 +1,5 @@ ------------------------------------------------------------------- wren ng thornton <wren@community.haskell.org> ~ 2012.09.26+-- wren ng thornton <wren@community.haskell.org> ~ 2014.03.30 ---------------------------------------------------------------- -- By and large Cabal >=1.2 is fine; but >= 1.6 gives tested-with:@@ -9,12 +9,12 @@ Build-Type: Custom Name: exact-combinatorics-Version: 0.2.0.4+Version: 0.2.0.7 Stability: experimental Homepage: http://code.haskell.org/~wren/ Author: wren ng thornton Maintainer: wren@community.haskell.org-Copyright: Copyright (c) 2011--2012 wren ng thornton+Copyright: Copyright (c) 2011--2013 wren ng thornton License: BSD3 License-File: LICENSE @@ -23,7 +23,7 @@ Description: Efficient exact computation of combinatoric functions. Tested-With:- GHC == 6.12.1+ GHC ==6.12.1, GHC ==7.6.1, GHC ==7.8.0 Extra-source-files: README, VERSION Source-Repository head
src/Math/Combinatorics/Exact/Binomial.hs view
@@ -88,7 +88,7 @@ #-} n `choose` k_ | n `seq` k_`seq` False = undefined- | 0 < k_ && k_ < n = + | 0 < k_ && k_ < n = k `seq` nk `seq` sqrtN `seq` foldl' (\acc prime -> step acc (fromIntegral prime))@@ -103,7 +103,7 @@ -- TODO: since we know the second operands to quot/rem are -- positive, we should use quotInt/remInt directly to avoid the -- extra tests (the overflow errors are not optimized away).- + k = fromIntegral $! if k_ > n `quot` 2 then n - k_ else k_ nk = n - k sqrtN = floor (sqrt (fromIntegral n) :: Double) `asTypeOf` n@@ -124,7 +124,7 @@ | n' `rem` prime < (k' `rem` prime) + r = go (n' `quot` prime) (k' `quot` prime) 1 $! p * prime | otherwise = go (n' `quot` prime) (k' `quot` prime) 0 p- + {- -- BENCH: apparently this is an unreliable optimization. | otherwise = acc * (prime ^ go n k 0 0) where
src/Math/Combinatorics/Exact/Factorial.hs view
@@ -109,7 +109,7 @@ -- -- fromIntegral s /= fromIntegral n - popCount (fromIntegral n) = error "factorial_splitRecursive: bug in the computation of n - popCount n" | otherwise = r `shiftL` s- + -- | The product of odd @j@s between n/2^k and 2*n/2^k. @len@ -- is the count of @j@ terms to multiply, where the @j@ state -- argument is the largest previously used term.@@ -123,7 +123,7 @@ in (,) <!> (qL*qR) <!> j'' where half = len `quot` 2- + (<!>) = ($!) -- fix associativity {-@@ -131,7 +131,7 @@ floorLog2 n | n <= 0 = error "floorLog2: argument must be positive" | otherwise = highestBitPosition n - 1- + highestBitPosition :: (Integral a, Bits a) => a -> Int {-# INLINE highestBitPosition #-} {-# SPECIALIZE highestBitPosition :: Int -> Int #-}@@ -204,7 +204,7 @@ go n | n < 2 = 1 | otherwise = (go (n `div` 2) ^ 2) * swing n- + swing n | n < 33 = smallOddSwing `unsafeAt` n | otherwise =@@ -230,7 +230,7 @@ return $ primorial (n `div` 2 + 1) n * xmathProduct primeList 0 count- + -- With hsc2hs we can use #def to define these as static C-style arrays, and then use base:Foreign.Marshall.Array to access them. Instead of using array:Data.Array.Unboxed; Or we could try the Addr# trick used in Warp smallOddSwing :: UArray Int Int32 smallOddSwing = listArray (0,32)@@ -238,7 +238,7 @@ , 429, 6435, 6435, 109395, 12155, 230945, 46189, 969969 , 88179, 2028117, 676039, 16900975, 1300075, 35102025 , 5014575, 145422675, 9694845, 300540195, 300540195 ]- + smallFactorials :: UArray Int Int64 smallFactorials = listArray (0,20) [ 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800@@ -263,10 +263,10 @@ where i2w :: Int -> Word i2w = fromIntegral- + w2i :: Word -> Int w2i = fromIntegral- + w1 = 0xaaaaaaaaaaaaaaaa -- binary: 0101... -- m1 = 0x5555555555555555 -- binary: 1010... m2 = 0x3333333333333333 -- binary: 11001100...